Leetcode String 中的有难度题目

字符串处理是面试中常见题型，较难的题目包括递归，动态规划，以及DFS等。
1，正则表达式匹配
‘.’ Matches any single character.
‘*’ Matches zero or more of the preceding element. * 号必须和前一个字符相关，这是和wildcard 匹配的区别。 这道题leetcode给出的解法用递归。下面来分析一下。
给定目标串S和模式串P，如果下一位上不是*，当前位的比较就很好办了：如果P当前位是*，返回错；如果S和P的当前位不相等返回错，否则这位匹配看下一位。
如果下一位是*，那就需要看当前位是否匹配：若是，1）P的当前位下一位*可以看做出现了0次，直接比较P下下位和S当前位；或者2)判断S的下一位和P当前位是否相等，若相等*可以看做P当前位出现了两次。若S和P当前位不匹配，那么S+2， P当前位和*视为出现了0次。

string 版本，加入^和$ Iterative 2.WildCard 匹配
*不需要和前一个字符挂钩，它可以是任意长度的任意字符串。因此直接比较当前位，如果当前位匹配则看下一位。否则，若当前位不是* 返回错。 若当前位是*，需要记录当前P的位置（*的位置）然后从P的下一位开始同S的当前位继续比较。直到有不匹配的，就返回来，从P的下一位和S的下一位开始比较。。。直到匹配成功。最后若S匹配完了，而且若P剩下的都是* 返回true，否则false

3. Text Justification
这道题思路并不难，但是非常难写，细节很多。总体思想是 依次读取word并加一个空格，直到下一个word超出行数L， 此时计算出现有的长度len，那么剩余的L-len用空格补齐而且要平均分配到各个word后面。

4. Edit Distance.
两个字符串str1 和str2，每一步只能有三个选择：增加一个元素，删除一个元素，转换一个元素。求转换的最小步数。 此题是典型的DP问题。dp[i][j] 表示str1[0,i)转换到str2[0,j) 需要的步数。显然dp[i][0]=i; dp[0][j]=j。 若str1[i]=str1[j], dp[i][j]==dp[i-1][j-1]; 否则有三种变化方法： str1[i]删掉，此时dp[i][j]=dp[i-1][j]+1;str2[j]删掉，此时dp[i][j]=dp[i][j-1]+1;str1[i]替换为str2[j],dp[i][j]=dp[i-1][j-1]+1。 这三个值取最小的。

5. Scramble String
两个字符串是Scramble String 的条件： 1. 两字符串相等。2，存在中间点i， str1中前i个字符组成的串和str2中前i个字符组成的串是scramble string而且 str1中i以后的字符组成的串和str2中i以后的字符组成的串是scramble string；3. 存在中间点i， str1中前i个字符组成的串和str2中后i个字符组成的串是scramble string而且str1中i以后的字符组成的串和str2中前n-i个字符组成串是scramble string。 先看DP解法： f[i][j][k] 代表了s1从i开始，s2从j开始，长度为k的两个substring是否为scramble string。
递归解法也很明了，注意substr(i)这个函数返回i以后一直到结尾的子字符串

6. Decode Ways.
主要是11-26这几个数有两重意义。  c[i] 表示decode ways of s[0,i-1]， 如果S[i-1]不等于0，c[i]=c[i-1]; 如果S[i-2]S[i-1] 是11-26这几个数，c[i] 还得加上c[i-2]

7.Restore IP Address
用DFS 思路比较简单， 每次取三个字符 abc, 分别看a, ab, abc是否是valid，如果是就保存下来，再取剩下的三个数，否则返回。注意如果不是最后一组字符串，要加上"."


8. Interleaving Strings
check s3 是不是s1 和s2的interleaving string. 这是一个典型的DP问题，需要二维DP。  f(i, j) == f(i, j-1) && s2[j-1] == s3[i+j-1)  OR f(i-1, j) && s1[i-1] == s3[i+j-1],
 i, j 代表 s1, s2 的长度，f(i, j) 表示 s1[0, i), s2[0, j) 是否可以interleaving 形成 s3[0, i+j)  解释一下这个公式： 如果s1的最后一个字符和s3最后一个字符相等，说明S3最后一个字符是S1最后一个字符做的贡献，因此把他俩去掉之后，若S1和S2能形成S3， 加上他俩也一定能，这就是f(i, j) ==  f(i-1, j) && s1[i-1] == s3[i+j-1]的意义。
9. Distinct Subsequences
也是一个典型的DP。 用 dp[i][j] 表示 the distinct seq number of T[0,i] in S[0,j]. 如果 T[i]!=S[j]. 说明S[j] 对结果没有贡献， dp[i][j]=dp[i][j-1] e.g ab a. S[1]!=T[0] hence dp[0][1]==dp[0][0]=1 如果 S[i]==T[j] 说明 S[i]对于结果做出来了贡献， dp[i][j]=dp[i][j-1]+dp[i-1][j-1] e.g abb ab S[2]==T[1] dp[1][2]=dp[1][1]+dp[0][1]=2 再更进一步，二维DP可以用一维DP取代
10. Count and Say
每一次从上一次的结果中计算求得，主要计算连续出现同一个数字的个数 11. Palindrome Partitioning I
此题求所有可能的切割方法使得每个字串都是palindrome 用DFS 详见 see here. No.16 11. Palindrome Partitioning II
此题是求最小的cut数，使得所有的substring是回文。 典型的DP问题： 设DP[i]: s[0..i] 最少切次数。 如果s[0..i]是回文就是0 否则： DP[i]=min{DP[j-1]+1} j 属于[1,i] 且s[j,i]是回文。 palin用来判断字串s[i..j]是否为回文。 12. word break I
给一个字符串和一个字典， 看能否把这个字符串分割为几个word，这几个word在字典中都能找到。 一维DP问题 F[j]表示S[0,j)是一个valid word， F[i]=true if F[j]=true and S[j,i)是valid word. 13. word break II
在上题基础上返回所有可能的word。典型的DFS问题，但是单纯DFS会超时。这里结合上一题用一个DP数组p保存结果 p[n+1]=true if s[0,n]可以被分割。