字符串面试题的特点 广泛性 1.字符串可以看做字符类型的数组，与数组排序、查找、调整有关 2.很多其它类型面试题可看作自字符串类型的面试题。
需掌握的概念 1.回文 题目(1) 判断一个字符串是否为回文 解法：递归 递归思路：一个回文字符串其中内部也是回文。所以，我们只需要以去掉两端的字符的形式一层层检查，每一次的检查都去掉了两个字符，这样就达到了缩少问题规模的目的。新问题与原问题有着相同的形式当去掉两端字符后的字符串，其产生的新问题同样是检查这个字符串是否回文。
递归的结束需要简单情景 ①. 字符串长度可能会奇数或偶数： 如果字符串长度是奇数，字符串会剩下最中间那位字符，但其不影响回文。当检查到长度为1的时候即代表此字符串是回文 如果字符串长度是偶数，当两端的字符串两两比较检查后不会剩下字符。即检查到长度为0的时候即代表此字符串是回文 ②. 如果检查到两端两个字符不相同。则说明此字符串不是回文，直接返回0，不需要继续检查
#include<iostream> #include<string> using namespace std; int huiwen(int low,int high,char str[],int length){ if(length==0||length==1){ return 1; } if(str[low]!=str[high]){ return 0; } huiwen(low+1,high-1,str,length-2); } int main(){ char str[20]; cin>>str; int length=strlen(str); int a=huiwen(0,length-1,str,length); if(a==1){ cout<<"回文！"; } else cout<<"不回文！"; }题目(2) 要求你，给你一个字符串，可在任意位置添加字符，最少再添加几个字符，可以使这个字符串成为回文字符串。 输入 第一行给出整数N（0
#include<iostream> #include<string> using namespace std; int huiwen(int low,int high,char str[],int length){ if(length!=0&&length!=1){ if(str[low]==str[high]){ return huiwen(low+1,high-1,str,length-2); } else return min(huiwen(low+1,high,str,length-1),huiwen(low,high-1,str,length-1))+1; } return 0; } int main(){ char str[20]; cin>>str; int res=0; int length=strlen(str); int a=huiwen(0,length-1,str,length); cout<<a; }第二种思路：（在我看来，该代码用到了动态规划，我还不太懂） 其实就是最长公共子序列的变种，将原序列str倒置后得到tmp。求出最长公共子序列的长度，则这些就是回文字串，剩下的就是没有匹配的字符的个数。用总长度减去最长公共子序列的长度，就得到需要添加的字符数量。 代码如下：
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> using namespace std; #define MAX 1010 int res[MAX][MAX]; int main() { int ncase, i, j; scanf("%d", &ncase); while(ncase--) { string str, tmp; cin>>str; tmp = str; reverse(tmp.begin(), tmp.end()); //倒置 for(i = 0; i < str.size(); ++i) { for(j = 0; j < tmp.size(); ++j) //res[i][j]为最长公共子序列的长度 { if(str[i] != tmp[j]) res[i + 1][j + 1] = max(res[i + 1][j], res[i][j + 1]); else res[i + 1][j + 1] = res[i][j] + 1; } } printf("%d\n", str.size() - res[i][j]); //总长度减去res[i][j]就是不匹配字符个数 } }2.子串（连续） 3.子序列（不连续） 4.前缀树（Trie树） 参考了博客trie树（前缀树）
#include<iostream> #include<string> using namespace std; #define MAX 26 //字符集大小 struct TrieNode{ bool isStr; //标识是否是一个完整的字符串 struct TrieNode *next[MAX]; }; /*插入*/ void Insert(TrieNode *root , char *word) { TrieNode *location=root; while(*word){ if(location->next[*word-'a']==NULL){ TrieNode *newNode=new TrieNode(); newNode->isStr=false; memset(newNode->next,NULL,sizeof(newNode->next));//初始化 location->next[*word-'a']=newNode; } location=location->next[*word-'a'];//location指向字符串在前缀树中下一个位置 word++; //当前字符在字符串中位置 } //字符串已经全部添加到前缀树 //标识前缀树到该节点位置为完整字符串 location->isStr=true; } //查找 bool Search(TrieNode *root , char *word) { TrieNode *location=root; while(*word&&location!=NULL){ location=location->next[*word-'a']; word++; } return(location!=NULL&&location->isStr ); } void Delete(TrieNode *location){ for(int i=0;i<MAX;i++){ if(location->next[i]!=NULL){ Delete(location->next[i]); } } delete location; } int main(){ //初始化前缀树的根节点，注意这里结构体指针的初始化 TrieNode *root=new TrieNode(); root->isStr =false; //前缀树中每一个节点的下一个节点，分配空间，注意memset的使用 memset(root->next,NULL,sizeof(root->next)); Insert(root,"a"); Insert(root,"bcd"); Insert(root,"xyz"); Insert(root,"abcdef"); if(Search(root,"bcd")) cout<<"exist"<<endl; else cout<<"no exist"<<endl; Delete(root); }5.后缀树和后缀数组 6.匹配 7.字典序
需掌握的操作 1.与数组有关的操作：增删改查 2.字符的替换 3.字符串的旋转
字符串题目常见类型 规则判断 1.判断字符串是否符合整数规则 2.判断字符串是否符合浮点数规则 3.判断字符串是否符合回文字符串规则 等等
数字运算 用字符串实现大整数 与大整数相关的加减乘除操作，需要模拟笔算的过程。
与数组操作有关的类型（重点） 1.数组有关的调整、排序等操作需要掌握 2.快速排序的划分过程，需要掌握和改写。
字符计数 1.哈希表 2.固定长度的数组（代替哈希表） 3.常见问题：滑动窗口问题，寻找无重复字符子串问题，计算变位词等问题。
动态规划问题 1.最长公共子串 2.最长公共子序列 3.最长回文子串 4.最长回文子序列 等
搜索类型 1.宽度优先搜索 2.深度优先搜索
高级算法与数据结构解决的问题 1.Manacher算法解决最长回文子串问题（马拉车算法） 2.KMP算法解决字符串匹配问题 3.前缀树结构 4.后缀树与后缀数组 5.通常面试很少出现。
