字符串，库函数，食之有味，弃之当可惜！但若长久时，面试官刷之，竟无语凝噎

C++的string提供接口size()可以方便地把握大小，而在c中字符串是以'\0'结尾的，判断语句为：

char a[5] = "asd";
for (int i = 0; a[i] != '\0'; i++) {
}

vector 和string其实一样，但是string有接口，重载了+，等等，用起来爽的。

反转字符串

344. 反转字符串 - 力扣（LeetCode） (leetcode-cn.com)

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

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

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

示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

可以使用   s.reverse()   来实现，但是核心代码还是自己写比较好

void reverseString(vector<char>& s) {
    for(int i=0,j=s.size()-1;i2;i++,j--){
        swap(s[i],s[j]);
    }
}

python原地修改

from typing import List

def reverseString(s: List[str]) -> None:
    """
    Do not return anything, modify s in-place instead.
    """
    left, right = 0, len(s) - 1
    

    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

s = ['n','c','k','j','h','f','e','q']
reverseString(s)
print(s)

反转字符串第二题

541. 反转字符串 II - 力扣（LeetCode） (leetcode-cn.com)

给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。

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

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

示例:

输入: s = "abcdefg", k = 2
输出: "bacdfeg"

• 主要是想清楚逻辑，什么时候可以反转那k个字符，反转的起始位置和结束位置怎么写

string reverseStr(string s, int k) {
    if(k==0) return s;
    for(int i = 0; i < s.size();i += 2 * k){
        //判断是否可以反转前k部分的字符
        if(i+k <= s.size()){
            //非核心代码，可以用接口
            reverse(s.begin()+i,s.begin()+i+k);
            continue;
        }

        //末尾字符不够k, 全部反转
        reverse(s.begin()+i,s.end());
        
    }
    return s;
    
}

剑指Offer 05.替换空格

剑指 Offer 05. 替换空格 - 力扣（LeetCode） (leetcode-cn.com)

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

示例 1：

输入：s = "We are happy."
输出："We%20are%20happy."

既然是替换，空间很可能是变大了

c++ 中的string 是可变的 所以 如果是' ' 变 '%20' 要考虑内存空间变大了

可以先增大空间，再重后向前修改数组减小复杂度

也可以说是用双指针。令i指向旧长度的末尾，j指向新长度的末尾，当i=j时就做完了替换：时间复杂度：$O(n)$, 空间复杂度：$O(1)$

string replaceSpace(string s) {
    int count=0;
    int oldSize = s.size();
    for(int i=0;i){
        if(s[i]==' '){
            count++;
        }
    }
    //重新修改大小
    s.resize(s.size()+2*count);
    //从后向前修改-双指针
    int newSize = s.size();
    for(int i=oldSize-1,j=newSize-1;i){
        if(s[i]!=' '){
            s[j]=s[i];
        }else{
            s[j]='0';
            s[j-1]='2';
            s[j-2]='%';
            j-=2;
        }
    }
    return s;
}

如果是用python写，可以用切片操作一次性替换掉'%20'

        ...
        left, right = len(s) - 1, len(res) - 1

        while left >= 0:
            if res[left] != ' ':
                res[right] = res[left]
                right -= 1
            else:
                # [right - 2, right), 左闭右开
                res[right - 2: right + 1] = '%20'
                right -= 3
            left -= 1
        ....

翻转字符串里的单词

151. 翻转字符串里的单词 - 力扣（LeetCode） (leetcode-cn.com)

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

• 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
• 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个
• 不要使用辅助空间，空间复杂度要求为$O(1)$。

题解：

首先要去除头尾空格，再去除重复空格，然后反转各个单词。

反转各个单词怎么做？可以先反转整个字符串，然后逐个单词再做翻转。

移除冗余空格

移除空格很难吗？当然，移除之后字符串变小了，位置要做改动，参考卡哥代码随想录 (programmercarl.com)

如果用erase来做，一个erase是$O(n)$的操作，如果外面加一层for循环，就是$O(n^2)$了，所以说，自己写移除空格算法：

使用双指针法来去移除空格，最后resize（重新设置）一下字符串的大小，就可以做到$O(n)$的时间复杂度。

//双指针法 移除空格算法 O(n)O(1)
void removeExtraSpaces(string& s) {
    int slowIndex = 0, fastIndex = 0; // 定义快指针，慢指针
    // 去掉字符串前面的空格
    while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {
        fastIndex++;
    }
    for (; fastIndex < s.size(); fastIndex++) {
        // 去掉字符串中间部分的冗余空格
        if (fastIndex - 1 > 0
            && s[fastIndex - 1] == s[fastIndex]
            && s[fastIndex] == ' ') {
            continue;
        }
        else {
            s[slowIndex++] = s[fastIndex];
        }
    }
    if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { // 去掉字符串末尾的空格
        s.resize(slowIndex - 1);
    }
    else {
        s.resize(slowIndex); // 重新设置字符串大小
    }
}

如果仅仅只是移除元素可以这样写：

// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
public:
    int removeElement(vector& nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (val != nums[fastIndex]) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};

翻转单词

可以用reverse（begin, end）来做, 或者自己写swap核心代码

    // 反转字符串s中左闭又闭的区间[start, end]
    void reverse(string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }

总体代码

class reverseWordSolution {
public:
    void removeExtraSpaces(string& s) {
        int slowIndex = 0, fastIndex = 0; // 定义快指针，慢指针
        // 去掉字符串前面的空格
        while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {
            fastIndex++;
        }
        for (; fastIndex < s.size(); fastIndex++) {
            // 去掉字符串中间部分的冗余空格
            if (fastIndex - 1 > 0
                && s[fastIndex - 1] == s[fastIndex]
                && s[fastIndex] == ' ') {
                continue;
            }
            else {
                s[slowIndex++] = s[fastIndex];
            }
        }
        if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { // 去掉字符串末尾的空格
            s.resize(slowIndex - 1);
        }
        else {
            s.resize(slowIndex); // 重新设置字符串大小
        }
    }

    // 反转字符串s中左闭又闭的区间[start, end]
    void reverse(string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }


    string reverseWords(string s) {
        removeExtraSpaces(s);
        //反转字符串
        reverse(s, 0, s.size() - 1);
        //反转每个单词，判断空格位置
        for (int i = 0; i < s.size(); i++) {
            int j = i;
            while (j < s.size() && s[j] != ' ') j++;
            reverse(s, i, j - 1);
            //更新要反转的单词开始位置
            i = j;
        }
        return s;

    }

};

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

剑指 Offer 58 - II. 左旋转字符串 - 力扣（LeetCode） (leetcode-cn.com)

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。

• 比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
• 提升难度：不能申请额外空间，只能在本串上操作。

从上面那道反转单词题目我们知道，全局翻转+局部反转可以达到反转整串单词的目的，怎么实现部分左旋呢？

局部反转+局部反转+全局反转=部分左旋

 竟然写出了这样的代码：

class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s,0,n-1);
        reverse(s,0,s.size()-1);
        reverse(s,n,s.size()-1);
        return s;
    }
};

当然是错掉了, 正确调研reverse接口之后

string reverseLeftWords(string s, int n) {
    reverse(s.begin(),s.begin()+n);
    reverse(s.begin()+n,s.end());
    reverse(s.begin(),s.end());
    return s;
}

python可以使用切片和’+‘快速实现：

def reverseLeftWords(s: str, n: int) -> str:
    return s[n:] + s[0:n]

Knuth-Morris-Pratt （KMP）算法

KMP算法就是在一个字符串中找是不是包含另一个串。

当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

记录已经匹配的文本内容？

next数组，即前缀表，前缀表就是用来当一个子串匹配失败后，选择最好的位置重新匹配用的。

例如：要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。

当匹配到aabaab之后，发现不对劲，要换一个，那么从哪开始？a?第二个a? b? 

当然是第三个‘a’! 如何match到这个位置，就交给前缀表next数组。

next数组里的数字表示的是什么，为什么这么表示？

参考github项目oiwiki解答：前缀函数与 KMP 算法 - OI Wiki (oi-wiki.org)

参考Carl的KMP精讲：代码随想录 (programmercarl.com)

strStr()找子字符串

在字符串中查找子串：

28. 实现 strStr() - 力扣（LeetCode） (leetcode-cn.com)

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2

示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1

说明: 当 needle 是空字符串时，我们应当返回什么值呢？应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

 思路：按KMP算法，当匹配到不符合的子串时，需要确定下一个前缀开始的位置，怎么确定呢？构建next数组

class strStrSolution {
public:
    void getNext(int* next, const string& s) {
        int j = -1;
        next[0] = j;
        for (int i = 1; i < s.size(); i++) { // 注意i从1开始
            while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
                j = next[j]; // 向前回退
            }
            if (s[i] == s[j + 1]) { // 找到相同的前后缀
                j++;
            }
            next[i] = j; // 将j（前缀的长度）赋给next[i]
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int size_needle = needle.size();
        int * next = new int[size_needle];
        getNext(next, needle);
        int j = -1; // // 因为next数组里记录的起始位置为-1
        for (int i = 0; i < haystack.size(); i++) { // 注意i就从0开始
            while (j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
                j = next[j]; // j 寻找之前匹配的位置
            }
            if (haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动
                j++; // i的增加在for循环里
            }
            if (j == (needle.size() - 1)) { // 文本串s里出现了模式串t
                return (i - needle.size() + 1);
            }
        }
        delete [] next;
        return -1;
    }
};

重复的子字符串

459. 重复的子字符串 - 力扣（LeetCode） (leetcode-cn.com)

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

class isnsubStrSolution {
public:
    void getNext(int* next, const string& s) {
        next[0] = -1;
        int j = -1;
        for (int i = 1; i < s.size(); i++) {
            while (j >= 0 && s[i] != s[j + 1]) {
                j = next[j];
            }
            if (s[i] == s[j + 1]) {
                j++;
            }
            next[i] = j;
        }
    }
    bool repeatedSubstringPattern(string s) {
        if (s.size() == 0) {
            return false;
        }
        int size_s = s.size();
        int* next = new int[size_s];
        
        getNext(next, s);
        int len = s.size();
        if (next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0) {
            return true;
        }
        delete[] next;
        return false;
    }
};