初学字符串，从一道经典例题入手

作者 | 梁唐

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

今天的文章来聊聊字符串。字符串是算法中非常非常重要的一个领域，涉及到大量的算法和数据结构，也是比赛场中的必出题之一。

另外在日常的开发工作当中，字符串也是我们经常使用的数据结构。深入了解字符串的相关特性，也有助于我们后续的正式工作。

定义

关于字符串，C语言以及C++的定义是不同的。

在C语言当中，字符串其实就是指的字符数组，比如：char[10] arr。C语言当中规定，字符串的最后一个符号是\0。只要遇见了\0就视为字符串结束，哪怕数组还有剩余。

C语言中为我们提供了string.h的库函数来进行字符串的处理，常用的有strlen求字符串长度，strcmp字符串比较和strcat字符串拼接等。如果大家学习过C语言的话，相比对于这些都不陌生。

在C++中，由于引入了面向对象的概念，C++的STL库中提供了更成熟的string类来代表字符串。string类有些类似于vector<char>，除了支持size()求字符串长度以外，还支持其他vector的用法。和vector不同的是，string类还重载了+等运算符，我们可以使用+将两个字符串拼接，使用==判断字符串相等。

字符串相关的算法虽然多且复杂，但这个数据结构本身的内容却不多，就只有这么一些。接下来就让我们来看一道例题，亲自实践锻炼一下。

反转字符串中的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

分析

这题的题意不算复杂，但是要考虑的细节不少。比如字符串中间的空格可能不止一个，字符串首尾两端都可能有多个空格。再加上进阶中对于空间复杂度的限制的话，就显得非常棘手。

面对题目复杂棘手的情况，上来就通篇考虑滴水不漏是很难的。能化简问题降低难度的降低难度，不能降低难度的可以先从一个比较简单的情况或者特例开始分析。

暴力

如果没有任何限制，那么这题本能的思路就是使用类似split函数对字符串按照空格进行分隔，得到所有的单词。之后再将每个单词翻转拼接回去，得到答案。

借助于Python强大的库函数，整个过程只需要两行就足以搞定，甚至压缩压缩到一行也不是不可以。

class Solution:
    def reverseWords(self, s: str) -> str:
        words = [w for w in s.split(' ') if w != '']
        return ' '.join(words[::-1])

C++中虽然没有split和join函数，没办法这么顺畅地实现，但代码逻辑是一样的，只不过这两个函数的部分需要我们自行实现而已。

到这里，如果只是追求通过的话，那么已经达成目标了。接下来我们来想办法满足它进阶难度的要求：空间复杂度为

。

进阶

要使得空间复杂度为

，那么我们肯定不能把单词全部提取出来再构建答案了，只能修改原字符串得到答案。

如果我们把首尾没有空格并且单词和单词之间只有一个空格的字符串称为理想字符串。整理一下思路，整个过程由两个主要步骤构成：一个部分是将非理想字符串处理成理想字符串，第二个部分是将理想字符串按照题意的要求进行反转。这两个部分互相独立可以分开思考，先解决哪个都可以。

整体上建议采取先易后难，想通即丢的原则，一次思考一个部分，想到解法就完全放下去思考其他的部分，这样思维更加聚焦。

首先来看空格的去除，字符串首尾部分的空格比较容易处理。但字符串中间的多余空格则比较难办，我们要删除意味着要移动字符串。数组删除元素的复杂度我们都知道是

，那么整体的复杂度会蜕化成

。在本题1e4的量级下大概率会超时，所以我们不能直接删除。

不能直接删除又需要去除掉不需要的元素，这该怎么办呢？

关于这个问题需要一定题量的积累，需要用到一个自覆盖的技巧。即使用两个指针i, j一齐从下标0出发。当i指向的内容需要保留时就覆盖到j，j只在每次被覆盖时移动，i一直移动不停。这样当一轮遍历之后，[0, j)这个区间内就只剩下了我们希望保留的元素，对于j之后的内容不予理会即可。

int j = 0;
int n = s.length();
// 是否是单词之后的第一个空格
bool fb = false;
for (int i = 0; i < n; i++) {
    // s[i]不是空格时需要保留
    if (s[i] != ' ') swap(s[j++], s[i]), fb = true;
    else {
        // 或者s[i]是第一个空格也保留
        if (fb) {
            fb = false;
            swap(s[j++], s[i]);
        }
    }
}

while (s.back() == ' ') s.pop_back();

这样我们只需要一重循环就解决了多余空格的问题，复杂度为

。接下来思考字符串的反转问题，我们要将字符串内的单词顺序反转，这很麻烦因为单词的长度各不相同，使得我们也不能使用两指针的方式从前后开始交换。

解决这个问题有一个非常巧妙的方法，就是将整体字符串翻转。比如hello world变成dlrow olleh。虽然单词内字母的顺序也翻转了，但是每个单词应该在的位置都正确了。那么我们只需要再一个一个把单词内部的字符翻转过来即可。因为单词和单词之间都有空格连接，所以每次遇到空格就知道遇到了单词的结尾，只要再记录下单词的开头，把中间的字符顺序翻转即可。

整体字符串的翻转和单词内部字符的翻转复杂度都是

，所以累加在一起，这还是一个

的算法。

class Solution {
public:
    string reverseWords(string s) {
        int j = 0;
        int n = s.length();
        bool fb = false;
        for (int i = 0; i < n; i++) {
            if (s[i] != ' ') swap(s[j++], s[i]), fb = true;
            else {
                if (fb) {
                    fb = false;
                    swap(s[j++], s[i]);
                }
            }
        }

        while (s.back() == ' ') s.pop_back();
        
        // 翻转整个字符串
        reverse(s.begin(), s.end());

        // 末尾插入空格，这样可以不用特判最后一个字符串
        s.push_back(' ');
        
        // 记录单词开始的位置
        int l = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == ' ') {
                int r = i-1;
                while (l < r) {
                    swap(s[l++], s[r--]);
                }
                l = i+1;
            }
        }
        // 删除刚插入的空格
        s.pop_back();
        return s;
    }
};

到这里通过我们一步一步的思考，终于解决了问题。怎么样，这种抽丝剥茧逐渐逼近正解的过程是不是很有意思呢？