字符串总结

Posted on Edited on

字符串常用的库函数和模板

经典题型总结

1.字符串匹配问题

28. 实现 strStr()

Sunday 算法

主要思路：

从前往后进行匹配，匹配成功时，模式串和主串索引同时+1，指向下一个

如果匹配失败，关注的是主串中参与匹配的最末位字符的下一位字符

  • 如果该字符没有出现在模式串中，移动位数=模式串长度＋１(因为移动位数<模式串长度，都会失败)

    eg: sudbccsde 模式串为：sde,此时ｂ没有出现在模式串中，可以直接略过它，主串从b的下一个位置，与模式串从头匹配

  • 如果该字符出现在该模式串中，移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1，主串移动到该位置　和模式串从头开始匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Sunday( string mstr,string des){//mstr为主串,des为模式串,返回模式串在主串中第一次出现的位置，如果不存在返回-1
	int dlen  = des.size();
	int mlen = mstr.size();
	unordered_map< char ,int>  shift;
	for(int i=0;i<dlen;i++) shift[des[i]]=dlen-i;//如果des中有字符重复，最后存储的是最右侧对应的shift
	int n=mlen-dlen;
	int i=0;
	while(i<=n){//i参与匹配的子串的
		if( mstr.substr(i,dlen)== des) return i; //如果已经找到
		else{
				if(shift.find(mstr[i+dlen])!=shift.end()){
                    i+= shift[mstr[i+dlen]];
                }else{
                    i += dlen+1;
                }
		}
	}
	return -1;
}

2.字符串中的动规问题

5.最长回文子串

​ 思路：定义状态，设计状态转移方程

bool dp[i][j]表示str.substr(i,j-i+1)是否是回文字

动态转移方程: dp[i][j] = dp[i+1][j-1] && (str[i]==str[j])

记录使 dp[i][j]为true的j-i+1的最大值。

时间复杂度: O(n*n)

空间复杂度: O(n*n)

10. 正则表达式匹配

​ 思路：定义状态，设计状态转移方程

目标串　s ,模式串p

bool dp[i][j]表示s[0:i]和p[0:j]之间匹配的结果

３.字符串相关处理

71. 简化路径

利用堆栈的思路解决

如果遇到字符串，压入堆栈中，如果遇到.不变

巧用栈，但是由于

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:
    string simplifyPath(string path) {
            vector<string> dirs;
            int index = -1;
        for(auto ptr = path.begin();ptr!=path.end(); ){
            ++ptr;//把跟目录跳过去
            auto _split = find(ptr, path.end(),'/');
            string substr = string(ptr,_split);
           if(substr==".." ){
               if(index>=0)
                {
                    index--;
                    dirs.erase(dirs.end()-1);
                }
            }else if(substr!="."  &&  substr!=""){
               dirs.push_back(substr);   
                index++;
            }
            ptr=_split;
        }
        string ans ="";
        for(int i=0;i<dirs.size();i++){
            ans+="/";
            ans+=dirs[i]; 
        }
        if(ans==""){
            return "/";
        }
        return ans;
    }

8. 字符串转换整数 (atoi)

细节题。注意测试样例

  • 不规则输入，但是有效 “-3924dfa”,”+413”
  • 无效格式 “++1”,”++c”
  • 溢出数据

9.利用str模拟大数相加

10.Add Binary

4.有限自动状态机

确定有限状态自动机（以下简称「自动机」）是一类计算模型,能够回答某种形式的「对于给定的输入字符串 S，判断其是否满足条件 P」的问题。它包含一系列状态，这些状态中：

  • 有一个特殊的状态，被称作「初始状态」。
  • 还有一系列状态被称为「接受状态」，它们组成了一个特殊的集合。其中，一个状态可能既是「初始状态」，也是「接受状态」。

起初，这个自动机处于「初始状态」。随后，它顺序地读取字符串中的每一个字符，并根据当前状态和读入的字符，按照某个事先约定好的「转移规则」，从当前状态转移到下一个状态；当状态转移完成后，它就读取下一个字符。当字符串全部读取完毕后，如果自动机处于某个「接受状态」，则判定该字符串「被接受」；否则，判定该字符串「被拒绝」

注意：如果输入的过程中某一步转移失败了，即不存在对应的「转移规则」，此时计算将提前中止。在这种情况下我们也判定该字符串「被拒绝」

  • 如何挖掘所有可能的状态，得到一个完备的状态集？

    • 把字符串跟据要求或者特点分为不同的状态，用当前处理到字符串的哪个状态作为自动机的状态
    • 进一步确定「初始状态」和「接受状态」的集合

  • 跟据接受的内容，确定划分接受数据的类型

  • 确定状态转移的规则

    在c++中，可以用enum(枚举)存储自动机状态State，定义接受的数据类型(InputType)

    用unordered_map<State , unordered_map<InputType,State>>

相关例题

65. 有效数字

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Solution {

public: 
    enum status{
        start,
        int_sign,
        integer,//
        left_point,//
        without_left_point,
        exp,
        exp_sign,
        exp_part,//
        fraction//
    };

    enum input{
        digit,
        point,
        sign,
        eE,
        invaild
    };

    unordered_map<status,unordered_map<input,status> > shift{   
        {start, { {digit,integer},
                {point,without_left_point},
                {sign,int_sign},
                }},
        {int_sign,{{digit,integer},
                  {point,without_left_point}
                    }},
        {integer,{{digit,integer},
                {point,left_point},
                {eE,exp},//指数
                }},
        {left_point,{{digit,fraction},
                    {eE,exp}}},
        {without_left_point,{{digit,fraction}}},
        {exp,{{digit,exp_part},
            {sign,exp_sign}}},
        {exp_sign,{{digit,exp_part}}},

        {exp_part,{{digit,exp_part}}},
        {fraction,{{digit,fraction},
                {eE,exp}}}
    };
    
    input inputtype(char ch){
        input ans = invaild;
        if(ch>='0' && ch<='9'){
            ans = digit;
        }else if( ch =='e' || ch=='E'){
            ans = eE;
        }else if(ch=='+' || ch=='-'){
            ans = sign;
        }else if(ch=='.'){
            ans = point;
        }
        return ans;
    }

    bool isNumber(string s) {
        status ss = start;
        int n= s.size();
        for(int i=0;i<n;i++){
            input chtype = inputtype(s[i]);
            if(chtype==invaild){
                return false;
            }
            if(shift[ss].find(chtype)==shift[ss].end()){
                return false;
            }else{
                ss = shift[ss][chtype];
            }
        }
        if(ss==integer|| ss==left_point || ss==exp_part || ss==fraction){
            return true;
        }else{
            return false;
        }
    }
};