转载

String 相关

字符串类的题目往往是基本工的考察，当然也有好多其他变化，好多与字符串相关的与数组相关，好多题目可以转化为字符串题目的类型。

基本类型

规则判断字符串是否符合整数浮点数回文
数字运算 int long 范围有限与大整数相关的加减乘除
与数组的排序查找有关的操作快排划分
字符计数与哈希表结合用固定长度的数组代替 hash表某种类型字符的出现次数滑动窗口寻找最长无重复子串计算变位词
动态规划类型最长公共子串最长公共子序列最长回文子串最长回文子序列
搜索类型宽度优先搜索深度优先搜索
使用高级算法与数据结构 Manacher算法（求最长回文子串） KMP 字符串匹配高级的数据结构：前缀树后缀树后缀数组面试中不会这么难

字符串的基本匹配 c++ 中有些还没有提供

比如split操作，按照某个指定的字符，将旧的字符串切分成字符串数组返回。这个可以说是字符串操作常见的基本操作了，比如之前微软校招的那个机试题，在字符串进行处理的时候，一个ip传过来，中间有“/”，有子网掩码，然后其中还有".“，这就需要把整个串切开，然后一个一个数字的处理。一定要熟练到不用思考！！！

// 第一个参数为原字符串 第二个参数为切分后的字符串数组 第三个参数为 划分字符 // 可以根据实际情况把第二参数调整成为 vector<string> 或者是vector <int> void split(string str,string strarray[], char c){     int len=str.size();     int i;     int leftindex=0;     int rightindex=0;     int count=0;     while(rightindex<len){        while(rightindex<len && str[rightindex]!=c)            {rightindex++;}        strarray[count]=str.substr(leftindex,rightindex-leftindex);        count++;        leftindex=rightindex+1;        rightindex=rightindex+1;     }}

基本匹配算法(普通匹配->KMP)

基本的基于两指针的字符串匹配，判断str1中是否包含str2，下一个题目中也用到了

static bool compare(vector<char>a,vector<char>b){     int lena=a.size();     int lenb=b.size();     int indexa,indexb;     if(lena<lenb){         return false;     }     for(indexa=0;indexa<=lena-lenb;indexa++){         for(indexb=0;indexb<lenb;indexb++){             if(a[indexa+indexb]!=b[indexb]){                 break;             }             if(indexb==(lenb-1)){                 return true;             }         }     }     return false; }

判断子树匹配（树形转字符串）

给定两颗彼此独立的树，头结点分别是t1以及t2，判断t1中是否有与t2树拓扑结构 完全相同 的子树。

思路1 从t1中开始遍历树，每次与t2进行比较，若是t2也对应着遍历完成了，就ok。
思路2 把t1与t2都转换为str，注意这里转化的时候有技巧如果按照某种序列遍历的时候发现遍历到叶子节点指针为null的时候一定要记得插入特殊字符这样才能保证序列与树结构是一一对应的之后采用kmp算法，或简单的字符串匹配算法，比较str1中是否包含str2。

/*思路1 注意递归的时候 还是写的不太流畅 递归的时候 不要把while也弄进去(混乱了)         if(!if_contain){             if_contain=traverse(A->left,B);             } 这部分开始的时候，每次的递归函数都写成了traverseandcompare就通不过测试， 因为在下一层遍历的时候，应该是同样的级别的， 下一层的根节点开始，与第二个树丛根节点开始一起向下进行递归遍历。 */ /* struct TreeNode {     int val;     struct TreeNode *left;     struct TreeNode *right;     TreeNode(int x) :             val(x), left(NULL), right(NULL) {     } };*/ class IdenticalTree { static bool traverse(TreeNode* A,TreeNode*B){     bool if_contain=false;     if(A!=NULL&&B!=NULL){         if_contain=traverseandcompare(A,B);         if(!if_contain){             if_contain=traverse(A->left,B);             }         if(!if_contain){             if_contain=traverse(A->right,B);          }          }         return if_contain; } static bool traverseandcompare(TreeNode* A,TreeNode*B){     bool left_compare,right_compare;       if (A==NULL&&B==NULL){         return true;     }     if(A==NULL||B==NULL){         return false;     }     if (A->val!=B->val){          return false;        }     left_compare=traverseandcompare(A->left,B->left);     right_compare=traverseandcompare(A->right,B->right);     return left_compare && right_compare;        } public:     bool chkIdentical(TreeNode* A, TreeNode* B) {         // write code here         bool value=traverse(A,B);         return value;     } };

思路2 注意tree的转换操作 最好情况下 匹配是通过 KMP 算法实现的 但是这里为了简单 就采用那种传统的两指针+减枝的遍历操作 注意第一层遍历的时候 indexa<=lena-lenb 这里要把 等号加上？ /* struct TreeNode {     int val;     struct TreeNode *left;     struct TreeNode *right;     TreeNode(int x) :             val(x), left(NULL), right(NULL) {     } };*/ class IdenticalTree { static void treetostr(TreeNode* A,vector<char> &str){         if (A==NULL){             str.push_back('#');             return ;         }           str.push_back((A->val)+'0');         treetostr(A->left,str);         treetostr(A->right,str);      } static bool compare(vector<char>a,vector<char>b){     int lena=a.size();     int lenb=b.size();     int indexa,indexb;     if(lena<lenb){         return false;     }     for(indexa=0;indexa<=lena-lenb;indexa++){         for(indexb=0;indexb<lenb;indexb++){             if(a[indexa+indexb]!=b[indexb]){                 break;             }             if(indexb==(lenb-1)){             return true;             }         }     }     return false; } public:     bool chkIdentical(TreeNode* A, TreeNode* B) {         // write code here         vector<char> astr;         vector<char> bstr;         treetostr(A,astr);         treetostr(B,bstr);         bool value=compare(astr,bstr);         return value;     } };

变形词（规则判断）

给定str1与str2，判断两个str是否为变形词。所谓变形词，str1与str2的字符种类一样，且每种字符中出现的

思路哈希表进行词频统计，之后比较两个表的记录是否ok，根据字符的ASCII长度生成hashmap，注意最后遍历的时候，检验的时候，范围是hashmap的范围这里是260之前总是弄错。。

class Transform { public:     bool chkTransform(string A, int lena, string B, int lenb) {         // write code here         int a[260] = {0};         int b[260];         memset(b,0,sizeof(b));         int i,j,index;         if(lena!=lenb){             return false;         }         for(i=0;i<lena;i++){             index=A[i];                     a[index]++;                      }                  for(j=0;j<lenb;j++){             index=B[j];             b[index]++;         }          for(i=0;i<260;i++){             if(a[i]!=b[i]){                 return false;             }         }         return true;     } };

以下几个题目都是字符交换类相关的通过活用局部字符交换的组合达到目的

旋转词（规则判断）

给定两个字符串，str1以及str2，判断str2是否为str1的旋转词。比如A=“12345”,A的旋转词有"12345",“23451”,“34512”,“45123"和"51234"。对于两个字符串A和B，请判断A和B是否互为旋转词。给定两个字符串A和B及他们的长度lena，lenb，请返回一个bool值，代表他们是否互为旋转词。

思路，如果A为12345 那么 AA 拼接起来，1234512345 这样的话 A的所有的旋转词，都在AA的子序列中，所以将问题转化成子序列问题，判断B是否为A的旋转词，只需要判断B是否为AA的子序列即可，转化成了一个字符串匹配的问题。str1str1拼接起来的序列穷举了所有的旋转词。
判断子序列的时候，快速的方法就是使用KMP，比较笨的方法，就是使用两指针，一次往后对比。
关于KMP的思路， Kmp在没有参考模板的时候，以自己的水平，短时间不太能写出来，这里先给一个笨办法的写法：

class Rotation {public:    bool chkRotation(string A, int lena, string B, int lenb) {        // write code here        string AA=A+A;        int i,j;        if(lena!=lenb){            return false;        }        for(i=0;i<lena+lena;i++){                int tempi=i;            for(j=0;j<lenb;){                if (AA[tempi]==B[j]){                    j++;                    tempi++;                }else{                    break;                }                if (j==(lenb-1)){                    return true;                }            }        }        return false;    }};

子句旋转

“pig loves dog” 旋转之后 “dog loves pig” 思路：

首先实现基本的旋转函数，采用的是两指针的思路，从两边往中间进行移动，并且两两进行交换，通过在字符串上的任意位置进行字符逆序的函数来实现。
先每个词局部旋转，“gip sevol god“ 之后在整体旋转 ”dog loves pig“

注意：reverse参数传递的时候要用到引用传递。还有一个坑，在分别reverse的时候，开始的时候都是以空格字符作为分隔符进行操作，实际上，在整个串遍历到最后位置的时候，也应该进行reverse操作，所以在判断条件的部分要考虑的充分一点，开始的时候这里没有注意到。

class Reverse { static void reverse(string &A,int left,int right){     char temp;     while(left<right){         temp=A[left];         A[left]=A[right];         A[right]=temp;         left++;         right--;     } } public:     string reverseSentence(string A, int n) {         // write code here         int len=n;         int i,left=0,right=0;         for(i=0;i<len;i++){             if(A[i]==' ' || i==(len-1)){                 if(i==(len-1)){                     right=i;                 }else{                     right=i-1;                 }                 reverse(A,left,right);                 left=i+1;             }         }         reverse(A,0,len-1);         return A;     } };

str平移

原str p1p2 ，移动之后变为p2p1，从第i个位置开始移动，str[0..i]的字符移动到右侧，之后将str[i+1…N]的字符移动到左侧，比如对于 “ABCDE” ，i的值为2，移动之后变为"DEABC"。思路

与上个题目类似，还是基于部分旋转的实现，首先是局部的旋转，p1逆反p2逆反，之后再整个序列进行逆反，结果还原为p2p1，就是所要求的最终结果。
按照以上思路，可以使用O(1)的空间实现结果，不使用额外的字符数组。

字符串拼接之后得到字典顺序较小的一组

比如[ “de” “abc”] 拼接之后，字典顺序较小的一组为[“abc” “de”] 这个题目的 实质为字符串数组的排序问题 ，主要是 比较函数的实现 ，比如str1以及str2。

策略（比较函数的实现）如果发现 str1+str2<str2+str1的话，则str1排在str2的前面，按照排序那套的理论，就是str1比str2还要小。
不是比较两个字符串各自的字典顺序，而是比较两个字符串在拼接完成之后的字典顺序。

要注意 string 对于< 进行了重载的操作没有必要把它转化为字符串数组才进行比较

class Prior {  static bool cmp(string a,string b){     string ab=a+b;     string ba=b+a;     return ab<ba; } public:     string findSmallest(vector <string> strs, int n) {         // write code here         string lastvalue="";         sort(strs.begin(),strs.end(),cmp);         int i=0;         int len=strs.size();         for(i=0;i<len;i++){             lastvalue=lastvalue+strs[i];         }         return lastvalue;     } };

字符替换

给定一个字符串str，将其中所有空格字符替换成“%20”，假设str后面有足够的空间。

替换的时候回涉及到大量的字符的移动
之前有类似的题目就是两个字符串合并的题目利用从后往前的拷贝顺序进行操作
首先找出需要替换的元素的个数，之后计算好最后一个空间，之后从后往前开始拷贝。

注意：

这个题目上，思路比较简单，但是有一些tricks，比如在第一次遍历的时候，count=0的时候直接返回。
string直接进行resize，iniString.resize(total)，这样相当于申请了新的空间。
由于最后申请的空间可能会大一些，最好再最后通过substr直接从大的字符串中截取小的字符串。

class Replacement { public:     string replaceSpace(string iniString, int length) {         // write code here         int i,j;         int count=0;         for(i=0;i<length;i++){             if(iniString[i]==' '){                 count++;             }         }         if(count==0){             return iniString;         }         int total=length+count*3;         iniString.resize(total);         for(i=total-1,j=length-1;i>=0,j>=0;){             if(iniString[j]==' '){                 iniString[i]='0';                 i--;                 iniString[i]='2';                 i--;                 iniString[i]='%';                 i--;                 j--;             }else{                 iniString[i]=iniString[j];                 i--;                 j--;             }         }          string newString=iniString.substr(i+1,total-1);          return newString;     } };

括号的有效组合

给定一个字符串str，判断是不是整体有效的括号字符串。比如str=“()"返回true，str=”()(“返回false。

思路其实比较easy，遍历的过程中使用一个变量number来保存括号出现的次数，左括号，number+1，右括号，number-1，之后在遍历的过程中，如果number<0，就为false。这个代码比较直接，就不在罗列了。

最长无重复字符串（较难一个注意这种思路）

给定一个字符串str，求其中无重复字符串的长度。 str=“abcd” 返回 4 ， str=“abcb” 返回3。

思路1 遍历string中的元素，使用map记录这个元素上一次出现的位置，之后更新，不能适用于所有的情况。

//错误版本：还是有一些通不过 class DistinctSubstring { public:     int longestSubstring(string A, int n)     {         // write code here         int i;         int max=0,span=0,index=0,left=0;         char current;         map<char,int> m;         map<char,int>::iterator iter;         for(i=0; i<n; i++)         {             current=A[i];             iter=m.find(current);             if(iter==m.end())             {                 m[current]=i;             }             else             {                 left=iter->second;                 span=i-left;                 m[current]=i;                 index=(left+1);             }         }          if(span>max)         {             max=span;         }         if((n-index)>max)         {             max=(n-index);         }         return max;     } };

思路二使用了有点类似于动态规划的思路，就是有点逐层递推的感觉，用s[i]代表以当前节点为最后一个元素的时候，最长无重复字符子串的长度。比如s[i-1]已经求出来，现在考虑如何通过s[i-1]来求取s[i] ，关键之要找到其中的这种递推的思路。
大致可以参考下这个图：首先通过map找到当前位置的元素上一次出现的位置，如果map中没有存储之前的元素，则pre++，如果找到，又分两种情况，图中的B表示的是，上一个元素能达到的最左边的位置。如果B的位置在lastindex的左边，则pre为lastindex的下一个元素到当前元素的距离。如果B的位置在lastindex的右边，则pre为上一个元素的最长无重复子序列能到达的最左边位置到当前元素的距离。之后每次查看pre，保存其最大值。

//通过的版本 class DistinctSubstring { public:     int longestSubstring(string A, int n)     {         // write code here         map<char,int>m;         int pre=0;         int i=0;         m[A[i]]=i;         i++;         pre=1;         int max=0;         map<char,int>::iterator iter;         for(i=1; i<n; i++)         {             iter=m.find(A[i]);             if(iter==m.end())             {                 pre++;                 m[A[i]]=i;             }             else              {                 int lastindex=iter->second;                 m[A[i]]=i;                 if((i-pre)<=lastindex)                 {                     m[A[i]]=i;                     pre=i-(lastindex+1)+1;                 }                 else                 {                     pre=pre+1;                 }             }             if(max<pre)             {                 max=pre;             }         }         return max;     } };