算法题-字符串相关
字符串
双指针法
剑指 Offer 05. 替换空格 - 力扣（Leetcode）
请实现一个函数，把字符串 s 中的每个空格替换成”%20”。
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
首先扩充数组到每个空格替换成”%20”之后的大小。
然后从后向前替换空格，也就是双指针法，过程如下：
i指向新长度的末尾，j指向旧长度的末尾。
其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
这么做有两个好处：
- 不用申请新数组。
- 从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| string replaceSpace(string s) {
int count=0;
for(auto c:s){
if(c==' ') count++;
}
int j=s.size();
s.resize(s.size()+count*2);
int i=s.size();
for(;j<i;i--,j--){
if(s[j]!=' '){
s[i]=s[j];
}else{
s[i]='0';
s[i-1]='2';
s[i-2]='%';
i-=2;
}
}
return s;
}
|
反转系列
当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。
541. 反转字符串 II - 力扣（Leetcode）
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
- 如果剩余字符少于
k 个，则将剩余字符全部反转。
- 如果剩余字符小于
2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
1
2
3
4
5
6
7
8
9
10
| 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);
else reverse(s.begin()+i,s.end());
}
return s;
}
};
|
151. 反转字符串中的单词 - 力扣（Leetcode） 快慢指针移除元素
给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public:
void reverse(string &word,int start,int end){
for(int i=start,j=end;i<j;i++,j--){
swap(word[i],word[j]);
}
}
void removespace(string &s){
int slow=0,fast=0;
for(;fast<s.size();fast++){
if(s[fast]!=' '){
if(slow!=0) s[slow++]=' ';
while(fast<s.size()&&s[fast]!=' '){
s[slow++]=s[fast++];
}
}
}
s.resize(slow);
}
string reverseWords(string s) {
removespace(s);
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;
}
};
|
KMP
KMP中的next数组是一个前缀表，前缀表是用来回退的，记录了模式串与主串不匹配的时候，模式串应该从哪里开始重新匹配
前缀表：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀
当不匹配的时候 找前一个字符的前缀表的数值，因为要找前面字符串的最长相同的前缀和后缀 因为到了这个点 比如说“f” 那么f前面的肯定经过了检验是匹配的
这个是后缀 下次匹配不必要从头开始 因为前缀就等于后缀了 相当于知道肯定匹配了
所以从b开始再匹配
时间复杂度由O（nm）到O（n+m）
构建next数组
1
2
3
4
5
6
7
8
9
10
11
12
13
| void getNext(int* next, const string& s){
int j = -1;
next[0] = j;
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;
}
}
|
28. 找出字符串中第一个匹配项的下标 - 力扣（Leetcode）
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
其实构建next数组和使用next数组的代码差不多
但是构建时是小串间比 注意j+1 因为下标从0开始
使用next数组是next数组本身不参与比较 只是作为j的回退使用 比较的是大串和小串
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
void getNext(int* next,string needle){
int j=-1;
next[0]=j;
for(int i=1;i<needle.size();i++){
while(j>=0&&needle[i]!=needle[j+1])
j=next[j];
if(needle[i]==needle[j+1]) j++;
next[i]=j;
}
}
int strStr(string haystack, string needle) {
if(needle.size()==0) return 0;
int* next=new int[needle.size()];
getNext(next,needle);
int j=-1;
for(int i=0;i<haystack.size();i++){
while(j>=0&&haystack[i]!=needle[j+1])
j=next[j];
if(haystack[i]==needle[j+1]){
j++;
}
if(j==(needle.size()-1)){
return i-needle.size()+1;
}
}
return -1;
}
};
|