【代码随想录】字符串

发表于 2024-01-08 更新于 2024-04-20 分类于代码随想录阅读次数：本文字数： 4.8k 阅读时长 ≈ 16 分钟

字符串基本理论

字符串看作是所有元素都是字符的线性表。

在C++种std::string表示字符串类型。

如果库函数仅仅是解题过程中的一小部分，并且你已经很清楚这个库函数的内部实现原理的话，可以考虑使用库函数。

反转字符串1

题目：第344题

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

思路：采用双指针法，一个指针在前，一个指针在后，交换两个指针指向的元素。然后两个指针同时移动。

class Solution {
public:
    void reverseString(vector<char>& s) {
        // 两个指针
        int front = 0;
        int tail = s.size() - 1;

        while (front < tail) {
            // 交换两个指针指向的元素
            char temp = s[front];
            s[front] = s[tail];
            s[tail] = temp;

            // 移动指针
            front++;
            tail--;
        }

        return;
    }
};

时间复杂度O(n)，两个指针共同遍历一次数组；空间复杂度O(1)

反转字符串2

题目：第341

给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。

如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例:

输入: s = “abcdefg”, k = 2
输出: “bacdfeg”

思路：直接取每个区间的起点，i=0， 2k，然后在循环中判断i + k是否超过最后字符串结尾即可。

class Solution {
public:
    void reverse(string &s, int front, int tail) {
        while (front < tail) {
            char temp = s[front];
            s[front] = s[tail];
            s[tail] = temp;

            // 更新两个指针
            front++;
            tail--;
        }
    }

    string reverseStr(string s, int k) {
        int len = s.length();
        for (int i = 0; i < len; i += 2 * k) {
            if (i + k <= len) {
                // 将[i, i + k)对应的字符翻转
                reverse(s, i, i + k - 1);
            } else {
                // 将[i, len)对应的字符翻转
                reverse(s, i, len - 1);
            }
        }

        return s;
    }
};

时间复杂度O(ceil(n/2k)*k)，其实就是字符串长度O(n);空间复杂度O(1)

替换空格

剑指Offer 05.替换空格

目前leetcode上没有原题，牛客网上有原题。

请实现一个函数，将一个字符串s中的每个空格替换成“%20”。

例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

数据范围:0≤len(s)≤1000 。保证字符串中的字符为大写英文字母、小写英文字母和空格中的一种。

思路：其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

这么做有两个好处：

1.不用申请新数组。

2.从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

首先遍历数组，计算空格的数目，然后重新分配合适的空间。

然后从后向前遍历原数组，填充元素。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string replaceSpace(string s) {
        // write code here
        int nums_blank = 0;
        for (char c : s) if (c == ' ') nums_blank++;

        // 重新分配一个字符串
        string result(s.length() + nums_blank * 2, 'a');
        int i = s.length() - 1;
        int j = result.length() - 1;
        while (i >= 0) {
            if (s[i] == ' ') {
                result[j--] = '0';
                result[j--] = '2';
                result[j--] = '%';
            } else {
                result[j--] = s[i];
            }
            i--;
        }

        return result;
    }
};

时间复杂度O(n)，遍历两次数组；空间复杂度O(n)

翻转字符串里的单词

题目：151

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：
输入: “the sky is blue”
输出: “blue is sky the”

示例 2：
输入: “ hello world! “
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：
输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

思路1：使用栈，栈种保存的类型是string，遍历字符串，遇到空格就取出之前的单词。

保存每个字符串并存入栈结构，最后再出栈，这样存储空间是O(n)

class Solution {
public:
    string reverseWords(string s) {
        // 创建字符串栈
        stack<string> words;

        // 遍历语句
        for (int i = 0; i < s.length(); i++) {
            if (s[i] != ' ') {
                // 找到下一个空格字符
                int j = i + 1;
                while (j < s.length() && s[j] != ' ') j++;

                // 将从i到j-1的字符作为字符串添加进栈
                words.push(string(s.begin() + i, s.begin() + j));

                i = j;
            } else continue;
        }

        // 输出结果
        string res = words.top();
        words.pop();
        while (!words.empty()) {
            res += " " + words.top();
            words.pop();
        }

        return res;
    }
};

注意上面将单词加入栈的逻辑：当遇到非空格字符时，一直向后找到空格字符，将单词入栈。

另一种逻辑是：遇到空格再将前面的单词加入栈，这样的坏处是：最后一个单词如果没有遇到空格就无法入栈。

时间复杂度O(n)；空间复杂度O(n)

思路2：去除多余的空格、翻转整个字符串、翻转单个字符串，存储空间是O(1)

删除多余的空格：首尾的空格以及单词之间连续的空格，参考题目：数组：1.1.3 题目27：移除重复元素

class Solution {
public:
    void removeBlank(string &s) {
        int len = s.length();
        // 快慢指针
        int slow, fast;
        slow = fast = 0;

        for (; fast < s.length(); fast++) {
            // 当快指针指向非空格字符时才添加字符
            if (s[fast] != ' ') {
                // 如果慢指针不是首部，则说明是单词中间，可以添加一个空格
                if (slow != 0) s[slow++] = ' ';
                // 移动快指针，将后面字符添加到这个单词上
                while (fast < s.length() && s[fast] != ' ')
                    s[slow++] = s[fast++];
            }
        }

        s.resize(slow);
    }

    // 翻转[start, end]内的字符串
    void reverse(string &s, int start, int end) {
        while (start < end) {
            swap(s[start], s[end]);
            start++;
            end--;
        }
    }

    string reverseWords(string s) {
        // 首先去除多余的空格字符
        removeBlank(s);

        // 翻转整个字符串
        reverse(s, 0, s.length() - 1);

        // 翻转每个单词
        for (int i = 0; i < s.length(); i++) {
            if (s[i] != ' ') {
                // 找到下一个空格字符
                int j = i + 1;
                while (j < s.length() && s[j] != ' ') j++;

                // 将[i, j-1]的之间的字串进行翻转
                reverse(s, i, j - 1);
                i = j; // 更新i为j指向的空格字符
            } else {
                continue;
            }
        }

        return s;
    }
};

时间复杂度O(n)；空间复杂度O(1)

左旋转字符串

题目：剑指Offer58-II.左旋转字符串

原leetcode上已经没有该题，牛客网上可以搜到原题

汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列 S ，请你把其循环左移 K 位后的序列输出。例如，字符序列 S = ”abcXYZdef” , 要求输出循环左移 3 位后的结果，即 “XYZdefabc”

思路1：需要额外空间：先保存前K个字符，然后将后面的字符移动到相应的位置。

时间复杂度O(n)；空间复杂度O(k)

思路2：（原地修改）旋转整个字符串、旋转左半字符串、旋转右半字符串

需要注意的是：如果K大于总长度，应该使用K%len进行翻转。另外如果总长度就是0，应该返回空字符串。

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @param n int整型
     * @return string字符串
     */
    void ReverseStr(string& s, int start, int end) {
        // 翻转[start, end]之间的子串
        while (start < end) {
            swap(s[start], s[end]);
            start++;
            end--;
        }
    }

    string LeftRotateString(string str, int n) {
        int len = str.length();
        if (len == 0) return str;
        int k = n % len; // 如果n大于等于字符串总长度
        // 翻转整个字符串
        ReverseStr(str, 0, len - 1);
        // 翻转前半部分字符串
        ReverseStr(str, 0, len - k - 1);
        // 翻转后半部分字符串
        ReverseStr(str, len - k, len - 1);


        return str;
    }
};

时间复杂度O(n)；空间复杂度O(1)

上面也可以直接使用C++ STL中的reverse函数。

旋转字符串回顾

此时我们已经反转好多次字符串了，来一起回顾一下吧。

在这篇文章344.反转字符串，第一次讲到反转一个字符串应该怎么做，使用了双指针法。

然后发现541. 反转字符串II ，这里开始给反转加上了一些条件，当需要固定规律一段一段去处理字符串的时候，要想想在for循环的表达式上做做文章。

后来在151.翻转字符串里的单词中，要对一句话里的单词顺序进行反转，发现先整体反转再局部反转是一个很妙的思路。

最后再讲到本题，本题则是先局部反转再整体反转，与151.翻转字符串里的单词类似，但是也是一种新的思路。

实现KMP算法

题目：28.

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

传统的字符串匹配算法：对于S串和T串。假设S串的长度为n，T串的长度为m，并且n 大于等于m，那么 i 遍历[0, n-1]， j 遍历[0, m - 1]，分别进行比较。时间复杂度O(mn)。

KMP算法主要思想：当在T串的比较中出现不同时，j 值（指向T串的字符下标）需要从头开始吗？i 值需要不断从 i 增加到i + m进行意义比较吗？

分析1：如果T串中全都是互不相同的字符：

当比较到不同的字符时，i 不需要进行回溯。

以T串的第一个字符为例，首字符不与后面的字符相等，即：$t_1 \ne t_2,…t_j$

而已经在本次循环中比较过S串和T串中的部分，即：$s_1=t_1,s_2=t_2,…s_j=t_j$

所以可得到：$t_1 \ne s_1,s_2,…s_j $

因此T串的首字符下一次比较不需要与$s_1…s_j$进行，直接从最后一个不相等的元素位置开始即可。

分析2：如果在T字符中出现重复字符

因此，如果在已经比较过的（指的是与S串中逐一比较过，即T串的左边部分）T串中有前缀和后缀相同的字串，那么由于后缀已经和S串比较过，存在相同的部分，所以只需要从S串中与前缀相同（也同样是与后缀相同）的后一位开始比较即可，即 j 是前缀的下一位，i 是上次循环比较的最后一次S串与T串中字符不相同的位置。

由此得到当比较到 j 不同时，下一步应该从T串的哪一个位置开始进行比较的next数组：

（注意，当 j 不同时，说明前面 [0, j-1]的T串子串与S串已经匹配上了，需要关注的是这一部分中的前缀和后缀长度）

当j=0时，说明在比较时T串的第一个字符就不相等，因此下一次仍然从0开始比较，即next[0]=0；
当j=1时，前面比较过相同的字符只有1个，因此下一次比较也只能从0开始，即next[1]=0；
当j>1时，前面比较过的和S串相同的字符是[0, j-1]，假设这一段的前缀和后缀的长度是K，k<j(整段的长度)，即前缀不能和后缀相同，则下一次比较从0+k开始，即next[j] = k。

获取next数组的代码：

void get_next(const std::string &T, std::vector<int> &next) {
    int i = 1, j = 0;
    int len = next.size();
    if (len > 0) next[0] = 0;
    if (len > 1) next[1] = 0;

    while (i < len - 1) {
        if (T[i] == T[j]) {
            // 第i个对应第i+1不匹配时的情况
            ++i;
            ++j;

            next[i] = j; // 当第i+1对应的字符不相等时，移动到前缀后的一个字符进行比较  
        } else if (j == 0) {
            // 如果不相等，但是j又是第一个字符
            ++i;
            next[i] = 0;
        } else {
            // j回溯，与字符串匹配时类似
            j = next[j];
        }
    }

}

在上面的代码中，j表示相同的前缀的下一个下标，i不断递增，遍历每一个字符，比较第 i 个字符，计算的前后缀长度是放到next数组的 i+1 位置上。

求next数组的时间复杂度：只涉及到对于串T的循环，所以时间复杂度是O(m)

KMP模式匹配：由于 i 不会再回溯，所以时间复杂度是O(n)

因此总的时间复杂度是O(m+n)，比传统的方法O((n-m+1)*m)要好一些。

需要注意的是，只有当子串中有很多重复部分，KMP才能体现出优势。

优化3：当出现不匹配时，要根据next数组选择 j 的位置，如果当前字符不与S串匹配，那么next指向的字符如果与当前字符相同，也不会与这个·S串中的字符相等，因此可以把next指向的字符对应next值给这个字符。

改进之后的求next数组：

void get_next(const std::string &T, std::vector<int> &next) {
    int i = 1, j = 0;
    int len = next.size();
    if (len > 0) next[0] = 0;
    if (len > 1) next[1] = 0;

    while (i < len - 1) {
        if (T[i] == T[j]) {
            // 第i个相等对应第i+1不匹配时的情况
            ++i;
            ++j;
            // 原始
            // next[i] = j;

            // 改进：这个过程描述的是当出现不匹配时，要根据next数组选择 j 的位置
            // 即当前字符不与S串匹配，那么考虑next指向的字符（也就是前缀字符）是否与当前字符相同
            // 如果相同说明两个字符都不会与这个S串中的字符相等，因此可以把next指向的字符（前缀字符）对应next值给这个字符
            if (T[i] != T[j]) next[i] = j; 
            else next[i] = next[j]; // 如果当前字符与前缀后的一个字符相等（也就是next[i]与i对应的字符相等）

        } else if (j == 0) {
            // 对应第一个字符就不等的情况
            ++i;
            next[i] = j;
        } else {
            // j回溯，与字符串匹配时类似
            j = next[j];
        }
    }

}

有了next数组之后，求第一个匹配的下标算法就很简单了：

int Index_KMP(const std::string &S, const std::string &T, int pos) {
    int s_len = S.length();
    int t_len = T.length();
    // 创建next列表
    std::vector<int> next(t_len);
    get_next(T, next);

    int i = pos; // i是S串下标
    int j = 0; // j是T串下标
    while (i < s_len && j < t_len) {
        // 如果对应字符相等
        if (S[i] == T[j]) {
            ++i;
            ++j;
        } else if (j == 0) {
            // 对应字符不等并且j是T串第一个字符
            ++i;
        } else {
            // 如果不等j回溯
            j = next[j];
        }
    }

    if (j == t_len) return i - t_len; // 如果找到了此时j就是T串的长度
    else return -1;
}

提交版本

class Solution {
public:
    // 求T串的next数组
    void GetNext(string &T, vector<int> &next) {
        int len = next.size();
        if (len > 0) next[0] = 0;
        if (len > 1) next[1] = 0;
        int i = 1; // i表示后缀
        int j = 0; // j表示前缀
        while (i < len - 1) {
            if (T[i] == T[j]) {
                ++i;
                ++j;

                if (T[i] != T[j]) next[i] = j;
                else next[i] = next[j];
            } else if (j == 0) {
                ++i;
                next[i] = 0;
            } else {
                j = next[j];
            }
        }
    }

    int strStr(string haystack, string needle) {
        int hay_len = haystack.length();
        int need_len = needle.length();
        vector<int> next(need_len, 0);
        GetNext(needle, next);

        int i = 0, j = 0;
        while (i < hay_len && j < need_len) {
            if (haystack[i] == needle[j]) {
                ++i;
                ++j;
            } else if (j == 0) {
                ++i;
            } else {
                j = next[j];
            }
        }

        if (j == need_len) return i - need_len;
        else return -1;
    }
};

重复的子字符串

题目：第459题

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

思路1：暴力破解法：假设存在子串s，字符串的总长度一定是子串s的整数倍，并且子串s一定是字符串的前缀。

此外，假设子串长度为i，那么任意的j > i，都有s[j] == s[j - i]

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int len = s.length();

        for (int i = 1; i < len; i++) {
            // i表示子串的长度
            if (len % i != 0) continue;
            // [0, i-1]是子串
            int j; // j是子串后面的字符
            for (j = i; j < len; j++) {
                // 如果长度为i的前缀是重复子串
                // 那么后面的每一个长度为i的子串应该与前面的子串相同
                if (s[j] != s[j - i]) break;
            }
            if (j == len) return true;
        }

        return false;
    }
};

时间复杂度O(n^2)；空间复杂度O(1)

思路2：利用两个s拼接在一起，一定能从中间找到s，因为如果是由重复字符串构成的话，中间的一部分一定是s。但是不能两端找到字串s，因为就是由两个s组成的。

find库函数的默认实现时间复杂度为KMP算法O(n)，空间复杂度为O(n)

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string temp = s + s;
        temp.erase(temp.begin());
        temp.erase(temp.end() - 1);

        if (temp.find(s) != std::string::npos) return true;
        else return false;
    }
};

思路3：在由重复子串组成的字符串中，最长相等前后缀不包含的子串就是最小重复子串

KMP算法的next数组其实就是最长前缀和最长后缀的概念，只不过我在实现的时候是求不包括当前字符的前缀长度

前缀和后缀的概念：

前缀：是指不包含最后一个字符的所有以第一个字符开头的连续子串

后缀：是指不包含第一个字符的所有以最后一个字符结尾的连续子串

作者求的是当前字符的前后缀长度，与我不同，所以作者遇到当前字符不同时，需要查找前一个字符的next值，我要找当前字符的next值，其实是一样的.

只不过作者引入了-1，我不想看了。

总结

字符串本质上就是字符数组。

如果要使用字符串的库函数，一定要了解库函数的实现复杂度。

双指针法：将字符串当作数组来处理，使用双指针可以一次遍历两遍数组。

反转：在反转字符串中的单词时，采用先整体反转再局部反转的方法；在实现字符串的左旋时，先局部反转再整体反转。

KMP算法：在字符串中寻找模式串。