切割字符串

问题来自一道算法题:

Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.

Please note that the string does not contain any non-printable characters.

Example:

Input: "Hello, my name is John"
Output: 5

使用空格作为分隔符，计算分隔符把字符串分割成了几个部分。

这个问题很容易解决，但是如果我们把字符串分割成几个部分，而非只计算字符串有几段呢？问题的例子就变成下面这样：

  Input: "Hello, my     name is John"
  Output: ["Hello", "my", "name", "is", "John"]

这个问题和python 中 split 函数所解决的问题是一样的，所以来看看Python是怎么实现的。

Py_LOCAL_INLINE(PyObject *)
STRINGLIB(split_whitespace)(PyObject* str_obj,
                        const STRINGLIB_CHAR* str, Py_ssize_t str_len,
                        Py_ssize_t maxcount)
{
    Py_ssize_t i, j, count=0;
    PyObject *list = PyList_New(PREALLOC_SIZE(maxcount));
    PyObject *sub;

    if (list == NULL)
        return NULL;

    i = j = 0;
    while (maxcount-- > 0) {
        while (i < str_len && STRINGLIB_ISSPACE(str[i]))
            i++;
        if (i == str_len) break;
        j = i; i++;
        while (i < str_len && !STRINGLIB_ISSPACE(str[i]))
            i++;
#ifndef STRINGLIB_MUTABLE
        if (j == 0 && i == str_len && STRINGLIB_CHECK_EXACT(str_obj)) {
            /* No whitespace in str_obj, so just use it as list[0] */
            Py_INCREF(str_obj);
            PyList_SET_ITEM(list, 0, (PyObject *)str_obj);
            count++;
            break;
        }
#endif
        SPLIT_ADD(str, j, i);
    }

    if (i < str_len) {
        /* Only occurs when maxcount was reached */
        /* Skip any remaining whitespace and copy to end of string */
        while (i < str_len && STRINGLIB_ISSPACE(str[i]))
            i++;
        if (i != str_len)
            SPLIT_ADD(str, i, str_len);
    }
    FIX_PREALLOC_SIZE(list);
    return list;

onError:
    Py_DECREF(list);
    return NULL;
}

这里大部分代码是在做分配内存的工作，去掉我们暂时不需要的部分，算法可以精简成如下:

class Solution {
public:
    int countSegments(string s) {
        int count = 0, i, j, str_len;
        char c = ' ';
        str_len = s.size();
        i = j = 0;
        while (i < str_len) {
            while (i < str_len && s[i] == c) 
                i++;
            if (i == str_len) break;
            j = i; i++;
            while (i < str_len && s[i] != c)
                i++;
            // 你可以把下标 i,j 之间的字符串append 到一个列表中，
            // 就可以实现把字符串按分隔符分割了。
            count++;
        }
        return count; 
    }
};