本文记录作者刷题过程中与字符串相关的题目。
一、分割字符串
1816. 截断句子（简单难度）
class Solution {
public:
/*解析：分割+截断+拼接
最简单的思路是先分割字符串为单词数组，然后反转数组元素，再拼接单词并添加上新的空格，
该思路的难点是根据空格分割字符串为单词数组*/
string truncateSentence(string s, int k) {
// 分割字符串为字符串数组
vector<string> words=splitWord(s);
// 截断字符串数组
vector<string> temp(words.begin(),words.begin()+k);
// 拼接为一个字符串
string res;
for(int i=0;i<temp.size();i++) {
if(i==0)res+=temp[i];
else{
res+=" ";
res+=temp[i];
}
}
return res;
}
vector<string> splitWord(string str){
vector<string> words;
string word;
for(char c:str){
// 遇到空格字符并且word有字符就添加word并且重置word，保证不会添加开头空格
if(c==' '&&word.size()>0){
words.push_back(word);
word="";
}
// 不添加空格
else if(c!=' '){
word+=c;
}
}
// str末位不一定有空格
if(word.size()) words.push_back(word);
return words;
}
};
二、反转字符串
344. 反转字符串（简单难度）
class Solution {
public:
/* 本题题意简单，难点在于原地修改字符数组，显然要使用双指针法，首尾交换即可*/
void reverseString(vector<char>& s) {
int left=0;// 左指针
int right=s.size()-1;// 右指针
// 反转字符串
while(left<right){
swap(s[left++],s[right--]);//交换
}
}
};
541. 反转字符串 II
/*本题的题意是反转一小段字符串中的固定长度，每隔 2k 个字符的就将前 k 个字符进行反转
显然只要实现一个反转指定区间[start,end]的reverse()函数，
接下来问题就变成了遍历指定区间即可*/
void reverse(string& s, int start, int end) {
int left = start;// 左指针
int right = end;//右指针
while(left < right){
swap(s[left], s[right]);
left++;
right--;
}
}
string reverseStr(string s, int k) {
// 遍历字符串[0,len),i每次增加2k
for(int i=0;i<s.size();i+=2*k){
// 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
if (i + k <= s.size()) {
reverse(s, i, i + k - 1);
}
else{
// 3. 剩余字符少于 k 个，则将剩余字符全部反转。
reverse(s, i, s.size() - 1);
}
}
return s;
}
151. 翻转字符串里的单词（中等难度）
剑指 Offer 58 - I. 翻转单词顺序（简单难度）
方法一：分割+反转+拼接
class Solution {
public:
/*解析：这道题是以空格分隔单词，难点在于开头、中间、结尾的空格数量都不确定。
方法一：分割+反转+拼接
最简单的思路是先分割字符串为单词数组，然后反转数组元素，再拼接单词并添加上新的空格，
该思路的难点是根据空格分割字符串为单词数组。
*/
string reverseWords(string s) {
// 分割字符串为字符串数组
vector<string> words=splitWord(s);
// 反转字符串数组
reverse(words.begin(),words.end());
// 拼接为一个字符串
string res;
for(int i=0;i<words.size();i++) {
if(i==0)res+=words[i];
else{
res+=" ";
res+=words[i];
}
}
return res;
}
vector<string> splitWord(string str){
vector<string> words;
string word;
for(char c:str){
// 遇到空格字符并且word有字符就添加word并且重置word，保证不会添加开头空格
if(c==' '&&word.size()>0){
words.push_back(word);
word="";
}
// 不添加空格
else if(c!=' '){
word+=c;
}
}
// str末位不一定有空格
if(word.size()) words.push_back(word);
return words;
}
};
方法二：原地双指针
class Solution {
public:
/*解析：这道题是以空格分隔单词，难点在于开头、中间、结尾的空格数量都不确定。
方法二：原地双指针（不容易想到）
因为该方法需要反转，所以从后向前遍历：
left，right都从最后一个元素出发，right先走到第一个字符处，left=right，走到第一个空格处
[left+1,right]就是单词所在索引区间，循环重复
*/
string reverseWords(string s) {
string res;// 结果字符串
int n = s.size();
if(n == 0) return res;
int left =n-1;// 左指针
int right = n - 1;// 右指针
while(right >= 0){
//从后往前寻找第一字符（如果不是空且没有到头，right就左移）
while(right >= 0 && s[right] == ' ') right--;
if(right < 0) break;
//从后往前寻找第一个空格
int left = right;
while( left >= 0 && s[left] != ' ' ) left--;
//添加单词到结果，单词所在位置[left+1,right]
res += s.substr(left + 1, right - left);
res += ' ';
//继续往前分割单词
right = left;
}
//去除最后一个字符空格
if (!res.empty()) res.pop_back();
return res;
}
}
186. 翻转字符串里的单词 II（中等难度）
/* 本题的是反转一个句子中的单词，难点在于必须使用原地算法，即双指针法。
先对每个单词进行reverse，再对整个字符串reverse，即可得到翻转单词顺序，但是单词中字母顺序不变的效果
因为是反转，所以从后向前遍历，left指针和right指针都指向字符串最后一个字符
right先从后向前寻找第一个字符，占据最后一个单词的right
left从left出发
*/
void reverseWords(vector<char>& s) {
int left = 0;//左指针
int right = 0;//右指针
int len = s.size();
while (left < len) {
// left从左到右找到第一个非空字符
while(left<len&&s[left]==' ') left++;
if(left>=len) break;//left不可以=len，后续要使用left
// right从left出发,找到第一个空字符
right=left;
while(right<len&&s[right]!=' ') right++;
// 反转[left,right-1]
reverse(s,left,right-1);
// 更新right
left=right;
}
reverse(s,0,len-1);
}
void reverse(vector<char>& s,int start,int end){
int left=start;
int right=end;
while(left<right){
swap(s[left],s[right]);
left++;
right--;
}
}
三、旋转字符串
剑指 Offer 58 - II. 左旋转字符串（简单难度）
class Solution {
public:
/*解析：本题的意思是将字符串的[0,n)移动到字符串的末尾
方法一：列表遍历拼接（借助额外内存空间）:先拼接[n,s.length())，再拼接[0,n)
方法二：列表遍历拼接（取余操作简化）
方法三：3次反转：反转[0,n);反转[n,s.length())；反转[0,s.length())
*/
string reverseLeftWords(string s, int n) {
//方法一：列表遍历拼接（借助额外内存空间）
// string res;
// // 获取[n,s.length())加入res中
// for(int i=n;i<s.length();i++){
// res+=s[i];
// }
// // 获取[0,n)加入res中
// for(int i=0;i<n;i++){
// res+=s[i];
// }
// return res;
//方法二：列表遍历拼接（取余操作简化）
// string res;
// int len=s.length();
// for(int i=n;i<n+len;i++){
// res+=s[i%len];
// }
// return res;
//方法三：巧妙反转
reverse(s.begin(),s.begin()+n);
reverse(s.begin()+n,s.end());
reverse(s.begin(),s.end());
return s;
}
};
796. 旋转字符串（简单难度）
class Solution {
public:
/*本题是判断s是否能够通过多次左旋转来得到goal
我们已经知道左旋转字符串的操作（剑指 Offer 58 - II. 左旋转字符串）
那么可以通过模拟左旋转来判断，左旋转的次数是有限的：1~s.length()
*/
bool rotateString(string s, string goal) {
// 旋转1~s.length()次
for(int n=1;n<=s.length();n++){
// 左旋转1个字符
reverse(s.begin(),s.begin()+1);
reverse(s.begin()+1,s.end());
reverse(s.begin(),s.end());
// 检查本次旋转后是否==goal
if(s==goal) return true;
}
return false;
}
};
四、匹配字符串
28. 实现 strStr()（简单难度）
class Solution {
public:
/*本题是字符串匹配的经典问题，在文本串txt中查找是否存在模式串ptn
方法一：暴力搜索：时间复杂度O(mn)，不需要额外空间
首先遍历文本串txt，让当前字符c和模式串的第一个字符ptn[0]比较，
如果相等就遍历ptn的其他字符串，看是否继续相等，不相等就退出内层循环。
方法二：KMP算法：花费更多空间，效率更高
*/
//获取前缀表(本质上就是一个dp数组)，其只和ptn有关
int* getNext(string& s) {
int n=s.size();
//初始next数组
int next[n];
next[0] = 0;//初始装填，next数组第一个一定是0
int j = 0;//j指向前缀末尾位置，从0开始，前缀的长度，前缀的指示长度
int i = 1;//i指向后缀末尾位置，从1开始
//遍历模式串ptn的最长后缀
for(; i < n; i++) //注意i从1开始
{
//如果后缀末尾字符和前缀末尾字符不一样，j回退
while (j > 0 && s[i] != s[j]) j = next[j-1];
//如果后缀末尾字符和前缀末尾字符一样，说明找到了相同的前后缀，则前缀++
if (s[i] == s[j]) j++;
// 记录此时前后缀的最长长度
next[i] = j;// 将j（前缀的长度）赋给next[i]
}
return next;
}
//获取前缀表(本质上就是一个dp数组)，其只和ptn有关
int* getNext1(string& s) {
int n=s.size();
//初始next数组
int next[n];
next[0] = -1;//j=0时，
int j = 0;//j指向前缀起始位置，从0开始，前缀的长度，前缀的指示长度
int i = -1;//当P[j]!=T[i]时，j指针的下一步移动位置
//遍历模式串ptn的前缀
while(j < n-1) //注意i从1开始
{
// 当前前缀字符和当前后缀字符相同
if (i == -1 || s[j] == s[i])
{
j++; i++;
next[j] = i;
}
else i = next[i];
}
return next;
}
int strStr(string txt, string ptn) {
//如果模式串为空，返回0
if(ptn=="") return 0;
//获取前缀表
int* next=getNext(ptn);
int j = 0;//负责遍历模式串的字符，和txt字符相同时移动，移动到末尾时说明匹配成功
//循环遍历文本串每个字符
for (int i = 0; i < txt.size(); i++) {
//如果txt当前字符和ptn当前字符不同，借助前缀表回溯模式串当前字符
while(j > 0 && txt[i] != ptn[j]) j = next[j-1];
//如果txt当前字符和ptn当前字符相同，ptn当前字符+1
if (txt[i] == ptn[j]) j++;
//如果j指向末尾，说明匹配完毕，返回txt的对应初始索引
if (j == ptn.size() ) return (i - ptn.size() + 1);
}
return -1;
}
};
459. 重复的子字符串（简单难度）
//获取前缀表(本质上就是一个dp数组)，其只和ptn有关
int* getNext(string& s) {
int n=s.size();
//初始next数组
int next[n];
next[0] = 0;//初始装填，next数组第一个一定是0
int j = 0;//j指向前缀末尾位置，从0开始，前缀的长度，前缀的指示长度
int i = 1;//i指向后缀末尾位置，从1开始
//遍历模式串ptn的最长后缀
for(; i < n; i++) //注意i从1开始
{
//如果后缀末尾字符和前缀末尾字符不一样，j回退
while (j > 0 && s[i] != s[j]) j = next[j-1];
//如果后缀末尾字符和前缀末尾字符一样，说明找到了相同的前后缀，则前缀++
if (s[i] == s[j]) j++;
// 记录此时前后缀的最长长度
next[i] = j;// 将j（前缀的长度）赋给next[i]
}
return next;
}
bool repeatedSubstringPattern(string s) {
//获取前缀表
int* next=getNext(s);
//如果next[len - 1] != 0则表示存在最长相等前后缀，如果数组长度可以被周期长度整除
int len = s.size();
if (next[len - 1] != 0 && len % (len - next[len - 1]) == 0) {
return true;
}
return false;
}
剑指 Offer 20. 表示数值的字符串（中等难度）
class Solution {
public:
/*该题是判断一个字符串是否可以表示为一个数值
字符串中可能存在首尾空格、小数点、e/E、正负号
1、空格只会出现在首尾，所以可以首先通过双指针法去除
2、正负号只能出现在首位或者e/E后一位
3、小数点只能出现一次，其前后至少有一个地方出现一个数字,不能出现e/E
4、e/E只能出现一次并且其前后都必须存在至少一个数字,不能出现小数点
5、整个字符串至少存在一个数字*/
bool isNumber(string s) {
if(s.length()==0) return false;
//去掉s的首尾部空格
int left=0,right=s.length()-1;
while(left<s.length()&&s[left]==' ') left++;
while(right>=0&&s[right]==' ')right--;
if(right>=left) s = s.substr(left,right-left+1);
else return false;
//
bool numFlag = false;// 是否出现数字，确保至少出现1个数字
bool dotFlag = false;//是否出现过一次小数点,确保只出现1次
bool eFlag = false;// 是否出现过一次e/E,确保只出现1次
// 遍历整个字符串
for (int i = 0; i < s.length(); i++) {
//如果是数字，numFlag设为true
if (s[i] >= '0' && s[i] <= '9') numFlag = true;
//如果是+/-，且出现在第1位或者e/E后一位，符合
else if ((s[i] == '+' || s[i] == '-') && (i == 0 || s[i-1] == 'e' || s[i-1] == 'E')) continue;
//如果是. 且之前没出现过也没出现过e/E, dotFlag = true;
else if (s[i] == '.' && !dotFlag &&!eFlag) dotFlag = true;
//判定为e，且之前没出现过也没出现过.并且出过数字
else if ((s[i] == 'e' || s[i] == 'E') && !eFlag && numFlag) {
eFlag = true;
numFlag = false;//为了避免e后面没有数字，出现e之后就标志为false
}
//其他情况，都是非法的
else return false;
}
return numFlag;
}
};
五、字符串排序
剑指 Offer 45. 把数组排成最小的数（中等难度）
class Solution {
public:
/*解析：本题是一个排序问题，但难点在于如何比较2个数？
小的数排在前面不一定数就小，例如3和30,330>303.
解决方案是将整数转成字符串，这样排序a和b两个数时，可以比较a+b和b+a谁更大
在代码实现时需要知道如何实现自定义排序方式
*/
// 自定义排序方式
static bool cmp(string& a,string& b){
return a + b < b + a;
}
string minNumber(vector<int>& nums) {
// 将整数数组转换为字符串数组
vector<string> strs;
for(int num:nums) strs.push_back(to_string(num));
// 自定义排序
sort(strs.begin(), strs.end(), cmp);
// 将字符串数组拼接为字符串
string res;
for(string s : strs) res+=s;
return res;
}
};
六、替换字符串
剑指 Offer 05. 替换空格（简单难度）
class Solution {
public:
/*本题是将字符串中的空格替换成指定的字符串，难点在于指定字符的长度大于1，不能直接替换原有的空格字符
方法一：额外空间
新建一个结果字符串，
遍历原有字符串，
如果当前字符是空格，就将替换字符串加入结果字符串；
否则就将当前字符加入结果字符串。
方法二：原地指针法
*/
string replaceSpace(string s) {
// 方法一：使用额外空间
// string res;
// for(char c:s) {
// if(c == ' ') res+="%20";
// else res+=c;
// }
// return res;
// 方法二：扩充原字符串大小，同时从后向前
int count = 0; // 统计空格的个数
int sOldSize = s.size();
for (int i = 0; i < s.size(); i++) {
if (s[i] == ' ') {
count++;
}
}
// 扩充字符串s的大小，也就是每个空格替换成"%20"之后的大小
s.resize(s.size() + count * 2);
int sNewSize = s.size();
// 同时从后向前遍历原有字符串，将空格替换为"%20"
// [0,Oldlen)
// [0, NewLen)
int fast=sOldSize - 1;// 负责遍历原字符串的字符
int slow=sNewSize - 1;// 负责指向
while(fast>=0||slow>=0){
if (s[fast] != ' ') {
s[slow] = s[fast];
} else {
s[slow] = '0';
s[slow-1] = '2';
s[slow-2] = '%';
slow-=2;
}
fast--;
slow--;
}
return s;
}
};
七、字典树
208. 实现 Trie (前缀树)（中等难度）
/ 字典树节点
struct TrieNode{
bool isEnd;// 从根节点到当前节点至此是否是一个完整的单词（该节点是否是一个单词的结尾）
vector<TrieNode*> children;//子节点数组，数组下标为[0,25],作为26个字母,存储子节点
TrieNode():isEnd(false),children(26){} // 构造函数
};
class Trie {
private:
TrieNode* root;
public:
Trie(){root = new TrieNode();}// 构造函数
// 向前缀树中插入字符串word
void insert(string word) {
// 按照word的字符，从根节点开始，一直向下走：
TrieNode* cur=root;//当前节点
for(char c:word){
int index=c-'a';
// 如果当前节点对应的子节点为空，就新建。不为空直接跳过
if(cur->children[index]==nullptr) cur->children[index]=new TrieNode();
cur=cur->children[index];//更新当前节点
}
cur->isEnd=true;//最后一个单词的节点是结尾
}
// 搜索字符串word是否在前缀树中
bool search(string word) {
// TrieNode* cur = root;
// for (char c:word) {
// int index=c-'a';
// if (cur->children[index] == nullptr) return false;
// cur=cur->children[index];//更新当前节点
// }
// return cur->isEnd;
return match(word, root, 0);
}
bool match(string word, TrieNode* node, int curIndex){
if(node==nullptr) return false;
if(curIndex==word.length()) return node->isEnd;// 当前索引已经越界，不必再递归
int index=word[curIndex]-'a';// 当前字符的索引
bool isExist=node->children[index] != nullptr;//当前节点的子节点是否对应当前字符
bool nextExit=match(word,node->children[index],curIndex+1);//当前节点子节点的子节点是否对应下一个字符
return isExist&&nextExit;
}
// 搜索是否存在前缀为prefix的word
bool startsWith(string prefix) {
TrieNode* cur = root;
for (char c:prefix) {
int index=c-'a';
if (cur->children[index] == nullptr) return false;
cur=cur->children[index];//更新当前节点
}
return true;
}
};
820. 单词的压缩编码（中等难度）
// 字典树节点
struct TrieNode{
bool isEnd;// 从根节点到当前节点至此是否是一个完整的单词（该节点是否是一个单词的结尾）
vector<TrieNode*> children;//子节点数组，数组下标为[0,25],作为26个字母,存储子节点
TrieNode():isEnd(false),children(26){}// 构造函数
};
// 字典树
class Trie{
TrieNode* root;
public:
Trie(){root = new TrieNode();}// 构造函数
//向字典树插入单词word
int insert(string word){
// 按照word的字符，从根节点开始，一直向下走：
TrieNode* cur=root;//当前节点
bool isNew = false;//是否是新插入单词
for(char c:word){
int index=c-'a';
// 如果当前节点对应的子节点为空，就新建。不为空直接跳过
if(cur->children[index]==nullptr) {
cur->children[index]=new TrieNode();
isNew = true;
}
cur=cur->children[index];//更新当前节点
}
cur->isEnd=true;//最后一个单词的节点是结尾
return isNew? word.length() + 1 : 0;
}
};
class Solution {
public:
/* 本题的题意是：给定多个单词，将其编码为一个助记字符串s，其中多个单词可能会由于后缀相同就合并到一起
要求返回助记字符串s的最小长度
思路：后缀字典树
后缀相同或者前缀相同，联想到字典树，考虑将所有单词加入反缀的字典树，
每次往字典树插入一个"新的word"时，就 += 该word的长度 + 1(#)
需要注意的是，我们必须先插入长单词，再插入旧单词
*/
static bool cmp(string a,string b){
return a.length()>b.length();
}
int minimumLengthEncoding(vector<string>& words) {
int res=0;
// 将单词词组按照单词长度从大到小排序，先插入长单词
sort(words.begin(),words.end(),cmp);
// 向字典树中插入所有单词
Trie* trie = new Trie();
for(string word : words){
reverse(word.begin(),word.end());//反转单词，因为我们定义的字典树是前缀树
res += trie->insert(word);//插入新单词，返回单词长度+1;插入旧单词，返回0
}
return res;
}
};
676. 实现一个魔法字典（中等难度）
// 字典树节点
struct TrieNode{
bool isEnd;// 从根节点到当前节点至此是否是一个完整的单词（该节点是否是一个单词的结尾）
vector<TrieNode*> children;//子节点数组，数组下标为[0,25],作为26个字母,存储子节点
TrieNode():isEnd(false),children(26){}// 构造函数
};
class MagicDictionary {
TrieNode* root;
public:
MagicDictionary() {root = new TrieNode();}
void insert(string word){
// 按照word的字符，从根节点开始，一直向下走：
TrieNode* cur=root;//当前节点
for(char c:word){
int index=c-'a';
// 如果当前节点对应的子节点为空，就新建。不为空直接跳过
if(cur->children[index]==nullptr) cur->children[index]=new TrieNode();
cur=cur->children[index];//更新当前节点
}
cur->isEnd=true;//最后一个单词的节点是结尾
}
void buildDict(vector<string> dictionary) {
for(string word:dictionary) insert(word);
}
bool search(string word) {
return match(word, root, 0, true);
}
bool match(string word, TrieNode* node, int start, bool hasChance){
if(start == word.length()){
return node->isEnd && !hasChance; // 因为"必须变一个字符"，因此 "&& !hasChance"
}
for(int i = 0; i < 26; i++){
if(node->children[i] != nullptr){
int index=word[start]-'a';
if(index == i && match(word, node->children[i], start + 1, hasChance))return true;
if(index != i && hasChance && match(word, node->children[i], start + 1, false))return true;
}
}
return false;
}
};