[LeetCode] 字符串完整版 — 双指针法 | KMP

基础知识

字符串的结尾：空终止字符00

char* name = "hello"; // 字符串不可拓展（由于是一个固定分配的内存块），有些地方必须加const
char name2[5] = {'h', 'e', 'l', 'l', 'o'}; // 字符数组没有空终止字符（非字符串）
char name2[6] = {'h', 'e', 'l', 'l', 'o', '\\0'}; // 或 0 
//strlen()（计算到空终止字符）

std::string基本是baseString类（模板类）的模板版本，模板参数是char

cplusplus_std::string

#include <string>
std::string name = "Hello"; // 默认const
std::cout << name << std::endl;
// .size(), .find() (不存在：std::string::npos)
// 没有contains函数，实现：
bool contains = name.find("no") != std::string::npos

宽字符：wchar_t

const char* name = u8"Hello"; // 1字节，utf8 std::string
const char16_t* name2 = u"Hello"; // 2字节，utf16 std::u16string
const char32_t* name3 = U"Hello"; // 4字节，utf32 std::u32string
const wchar_t* name4 = L"Hello"; // 2字节（由编译器决定，在大多数Unix/Linux系统上通常是32位）std::wstring

更多用法：

// 遍历字符串数组s，如：char s[5] = "asd";
for (int i = 0; s[i] != '\0'; i++) { }
// 遍历字符串s
for (int i = 0; i < s.size(); i++) { }string.resize(new_length, '\0'); // 截断/扩充 O(1)~O(n)
string.erase(index, len); // 删除字符，O(n)（删除后需前移），不传参数相当于clear()
string.erase(first, last); // 删除字符，参数为迭代器，不包含last，last非必须参数
string.clear(); // 清空字符串
getline(cin, string);  // 读取一整行，包含空格
reverse(string.begin(), string.end()); // 原地反转字符串 O(n)，<algorithm>中的泛型函数
string.find(substring, pos=0); // 寻找子串 O(m+n)，pos为起始查找位置，没有找到返回std::string::npos
string.substr(pos=0, len=npos); // 从字符串中提取子串 O(m)，pos为起始位置，len为字串长度

双指针法

344# 反转字符串

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

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

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

提示：

• 1 <= s.length <= 105
• s[i] 都是 ASCII 码表中的可打印字符

// 首尾指针
// O(n) 0ms; O(1) 26.59MB
class Solution {
public:void reverseString(vector<char>& s) {int left = 0, right = s.size() - 1;while (left < right) {swap(s[left++], s[right--]);}}
};

// swap()的两种实现
int tmp = s[i];
s[i] = s[j];
s[j] = s[i];s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];

541# 反转字符串II

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

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

示例 1：

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

示例 2：

输入：s = "abcd", k = 2
输出："bacd"

提示：

• 1 <= s.length <= 10^4
• s 仅由小写英文组成
• 1 <= k <= 10^4

当需要固定规律一段一段去处理时，考虑在for循环上做调整

// 344衍生，处理for循环条件
// O(n) 0ms; O(1) 9.43MB
class Solution {
public:string reverseStr(string s, int k) {for (int i = 0; i < s.size(); i += 2 * k) {if (i + k < s.size()) {reverse(s.begin() + i, s.begin() + i + k); // reverse不包括last} else {reverse(s.begin() + i, s.end());}}return s;}
}; 

54K 替换数字

题目链接

题目描述

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。

输入描述

输入一个字符串 s,s 仅包含小写字母和数字字符。

输出描述

打印一个新的字符串，其中每个数字字符都被替换为了number

输入示例

a1b2c3

输出示例

anumberbnumbercnumber

提示信息

数据范围：
1 <= s.length < 10000。

首先扩充数组到每个数字字符替换成 "number"之后的大小

再用双指针法，从旧尾向新尾替换字符

// 双指针法从后向前扩充数组
// O(n) 35ms; O(1) 2.18MB
#include<iostream>using namespace std;int main() {string s;while (cin >> s) {int n = s.size();int count = 0; // 统计数字for (int i = 0; i < n; i++) {if (s[i] >= '0' && s[i] <= '9') count++;}// 扩充字符串s.resize(n + count * 5);int s_oldTail = n - 1, s_newTail = s.size() - 1;while (s_oldTail <= s_newTail && s_oldTail >= 0) {if (s[s_oldTail] >= '0' && s[s_oldTail] <= '9') {s[s_newTail--] = 'r';s[s_newTail--] = 'e';s[s_newTail--] = 'b';s[s_newTail--] = 'm';s[s_newTail--] = 'u';s[s_newTail--] = 'n';s_oldTail--;}else {s[s_newTail--] = s[s_oldTail--];}}cout << s << endl;}return 0;
}

151# 反转字符串中的单词

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

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

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

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

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

• 1 <= s.length <= 10^4
• s 包含英文大小写字母、数字和空格 ' '
• s 中 至少存在一个 单词

在不追求空间复杂度的情况下，可以使用使用split库函数分隔单词，再定义一个新的string字符串把单词倒序相加

空间复杂度O(1)的解法：1. 移除多余空格；2. 反转字符串； 3. 反转单词

移除多余空格类似移除元素的思想：快慢指针法

// 移除多余空格
// 快慢指针
void removeExtraSpaces(string& s) {int slowIndex = 0, fastIndex = 0;int n = s.size();// 去除字符串首部空格while (n > 0 & fastIndex < n && s[fastIndex] == ' ') fastIndex++;// 去除字符串中间冗余空格while (fastIndex < n) {if (fastIndex > 0 && s[fastIndex] == ' ' && s[fastIndex] == s[fastIndex - 1]) {fastIndex++;} else {s[slowIndex++] = s[fastIndex++];}}// 去除字符串尾部空格if (slowIndex > 0 && s[slowIndex - 1] == ' ') s.resize(slowIndex - 1);else s.resize(slowIndex);
}

// 移除多余空格优化版：对整个单词操作，去除所有空格再添加
// 快慢指针
void removeExtraSpaces(string& s) {int slowIndex = 0, fastIndex = 0;while (fastIndex < s.size()) {if (s[fastIndex] != ' ') {if (slowIndex != 0) s[slowIndex++] = ' ';while (s[fastIndex] != ' ' && fastIndex < s.size()) s[slowIndex++] = s[fastIndex++];} else {fastIndex++;}}s.resize(slowIndex);
}

// 双指针法
// O(n) 0ms; O(1) 9.89MB
class Solution {
public:void reverse(string& s, int start, int end) {int i = start, j = end;while (i < j) {swap(s[i++], s[j--]);}}string reverseWords(string s) {// 去除多余空格int slowIndex = 0, fastIndex = 0;while (fastIndex < s.size()) {if (s[fastIndex] != ' ') {if (slowIndex != 0) s[slowIndex++] = ' ';while (s[fastIndex] != ' ' && fastIndex < s.size()) s[slowIndex++] = s[fastIndex++];} else {fastIndex++;}}s.resize(slowIndex);// 反转字符串reverse(s, 0, s.size() - 1);// 反转单词int start = 0;for(int i = 0; i <= s.size(); i++) {if (s[i] == ' ' || i == s.size()) {reverse(s, start, i - 1);start = i + 1;}}return s;}
};

55K 右旋字符串

题目链接

题目描述

字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。

例如，对于输入字符串 “abcdefg” 和整数 2，函数应该将其转换为 “fgabcde”。

输入描述

输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。

输出描述

输出共一行，为进行了右旋转操作后的字符串。

输入示例

2
abcdefg

输出示例

fgabcde

提示信息

数据范围：
1 <= k < 10000,
1 <= s.length < 10000;

把字符串看成两个部分size-n | n，反转两个部分：先整体反转所有字符，再两个部分分别反转（两个操作可交换先后顺序）

// 反转字符段：整体+局部
// O(n) 31ms; O(1) 2.18MB
#include<iostream>
#include<algorithm>using namespace std;int main() {int n;string s;while (cin >> n) {cin >> s;reverse(s.begin(), s.end());reverse(s.begin(), s.begin() + n);reverse(s.begin() + n, s.end());cout << s << endl;}return 0;
}

KMP 字符串匹配算法

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

前缀表：子串的最大匹配前后缀长度（用于记录模式串与主串(文本串)不匹配时，模式串应该从哪里开始重新匹配）

前缀函数的计算：判断与最大匹配前后缀长度prefix[i-1]处的下一个字符是否相等，若相等则prefix[i] = prefix[i-1] + 1；若不相等则回退数次直至相等或不存在

回退方式：找次长的匹配前后缀长度，即prefix[prefix[i - 1] - 1]

推荐教学视频：六分钟学会KMP

28# 找出字符串中第一个匹配项的下标

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

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

提示：

• 1 <= haystack.length, needle.length <= 10^4
• haystack 和 needle 仅由小写英文字符组成

// 前缀函数 
vector<int> getNext(const string& s) {vector<int> prefix(s.size(), 0);for (int i = 1, pre = 0; i < s.size(); i++) {while (pre > 0 && s[i] != s[pre]) {pre = prefix[pre - 1];}if (s[i] == s[pre]) prefix[i] = ++pre;}return prefix;
}

一种方法（启发式方法，利用前缀函数）：将模式串与主串合并，只需找到所需的该字符串的最大匹配前后缀的值（前缀函数==模式串长度）

// 合并模式串与主串，找最大匹配前后缀
// O(n+m) 0ms; O(n+m) 8.96MB
class Solution {
public:int strStr(string haystack, string needle) {int n = haystack.size(), m = needle.size();string s = needle + '#' + haystack;vector<int> prefix(s.size(), 0);for (int i = 1; i < s.size(); i++) {int pre = prefix[i - 1];while (pre > 0 && s[i] != s[pre]) {pre = prefix[pre - 1];}if (s[i] == s[pre]) {prefix[i] = pre + 1;if (prefix[i] == m) {return i - m * 2;}}}return -1;}
};

优化：只需生成模式串的前缀表后匹配

// KMP
// O(n+m) 0ms; O(m) 8.61MB
class Solution {
public:int strStr(string haystack, string needle) {int n = haystack.size(), m = needle.size();// 生成前缀表vector<int> prefix(m, 0);for (int i = 1, pre = 0; i < m; i++) {while (pre > 0 && needle[i] != needle[pre]) {pre = prefix[pre - 1];}if (needle[i] == needle[pre]) prefix[i] = ++pre;}// 匹配for (int i = 0, j = 0; i < haystack.size(); i++) {while (j > 0 && haystack[i] != needle[j]) {j = prefix[j - 1];}if (haystack[i] == needle[j]) {j++;if (j == needle.size()) {return i - j + 1;}}}return -1;}
};

时间复杂度：当前位的前缀函数至多比前一位增加一，每当回退一次，当前位的前缀函数的最大值都会减少。前缀函数的总减少次数不会超过总增加次数

KMP 算法虽然有着良好的理论时间复杂度上限，但大部分语言自带的字符串查找函数并不是用 KMP 算法实现的。这是因为在实现 API 时，我们需要在平均时间复杂度和最坏时间复杂度二者之间权衡。普通的暴力匹配算法以及优化的 BM 算法拥有比 KMP 算法更为优秀的平均时间复杂度

#459 重复的子字符串

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

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"
输出: false

示例 3:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

• 1 <= s.length <= 10^4
• s 由小写英文字母组成

移动匹配法：对字符串s，s+s内若能找到s，那么s一定可以由子串构成，反之亦然（可从充分必要性的角度证明）

// 移动匹配法
// O(n) 7ms; O(n) 13.33MB
class Solution {
public:bool repeatedSubstringPattern(string s) {string t = s + s;t.erase(t.begin());t.erase(t.end() - 1);if (t.find(s) != std::string::npos) return true;return false;}
};

KMP法：如果字符串s是由重复子串组成，那么最大匹配前后缀不包含的子串一定是s的最小重复子串，反之亦然（可从充分必要性的角度证明）

若s是由最小重复子串p组成，那么最大匹配前后缀一定由数个p组成（反证法），从而推出充分性

根据以上陈述，只需要判断不包含的子串是否是重复子串，且若是重复子串，那么一定是最小重复子串

不包含的子串长度若被s的长度整除，那么不包含的子串一定是（最小）重复子串，反之亦然

因此若要判断s是否由重复子串构成，只需判断最大匹配前后缀不包含的子串长度是否被s的长度整除

// 最大匹配前后缀
// O(n) 0ms; O(n) 15.18MB
class Solution {
public:bool repeatedSubstringPattern(string s) {int n = s.size();vector<int> prefix(n, 0);for (int i = 1, pre = 0; i < n; i++) {while (pre > 0 && s[i] != s[pre]) {pre = prefix[pre - 1];}if (s[i] == s[pre]) prefix[i] = ++pre;}if (prefix[n - 1] && n % (n - prefix[n - 1]) == 0) return true;return false;}
};

本文参考： LeetCode官方题解 、 代码随想录 及 六分钟学会KMP