字符串 DP 类的很多典型问题，用这一张图都能说明白：
两个 String 放一起，从某个位置开始看看是否 match; 要是不 match 了，就得错开一位看；要是 match 了，就都往后挪一位看。在 Edit Distance 里面，稍微特殊一点，因为我们还有一个 replace 操作，可以直接修正当前 mismatch，让两个字符串都挪动一格位置。
于是对于每一个 String，就有了一个对于其位置敏感的维度 dp[i]，代表从最左面开始的 i 个字符构成的字符串，也是子问题的结构定义。因为我们有两个 String 并且需要枚举位置之间可能的各种交错穿插，我们就需要两个维度 dp[i][j]，代表第一个字符串中的 i 个字符和第二个字符串中的 j 个字符匹配情况。
研究一个新问题时，最好还是从算法导论开始。
给定长度为 m 的字符串 {1,2,3...m} ，其 subsequences 的数量总数为 2^m，即对每个字符选择 “取 / 不取”。
于是有了下面的可视化版本~
这个版本的做法非常适合存储和输出 optimal path，也可以应用到 Longest Increasing Subsequence 中，用于 follow-up 情况下输出 sequence.
比如输入数组为 X = [x1, x2 .. xn]，其排序后的数组为 X' = [x'1, x'2 .. x'n]
LIS 即 X 与 X' 的 LCS，判断条件完全一样，元素相等向右下走。如果每一步上都存行进方向，那么最后从右下角往左上出发，每一步指向左上角的箭头都是 LIS 的元素。
滚动数组优化版的代码.
最大值肯定在 dp[][] 的最右下角。
Copy public class Solution {
/**
* @param A, B: Two strings.
* @return : The length of longest common subsequence of A and B.
*/
public int longestCommonSubsequence ( String A , String B) {
// write your code here
if (A == null || B == null ) return 0 ;
int n = A . length ();
int m = B . length ();
if (n == 0 || m == 0 ) return 0 ;
int [][] dp = new int [ 2 ][m + 1 ];
for ( int i = 1 ; i <= n; i ++ ){
for ( int j = 1 ; j <= m; j ++ ){
if ( A . charAt (i - 1 ) == B . charAt (j - 1 )){
dp[i % 2 ][j] = dp[(i - 1 ) % 2 ][j - 1 ] + 1 ;
} else {
dp[i % 2 ][j] = Math . max (dp[(i - 1 ) % 2 ][j] , dp[i % 2 ][j - 1 ]);
}
}
}
return dp[n % 2 ][m];
}
} 一开始未经思考尝试以 LCS 长度判断，但是这个思路是错的，因为 S 和 T 的 LCS 长度可以满足条件，但是 mismatch 的字符却不一定是在同一个位置 。况且， LCS 的时间复杂度是 O(mn), 这题应该很明显有 O(n) 的解法。
正解借鉴了论坛的代码，其实非常简洁。
核心思想是，既然有且只有 1 个位置 mismatch，我们可以直接在找到 mismatch 位置上判断：
如果 m == n ，mismatch 之后的子字符串一定完全相等；
否则长的那段在 i 之后的 substring 一定与短的以 i 开始的 substring 全等；
如果在循环末尾还没有发现 mismatch，两个字符串末尾必然会有 1 的长度差，否则 S == T.
在字符串 DP 中，原始字符串上的 substring，等价于原始区间内的 subproblem.
Copy public class Solution {
public boolean isOneEditDistance ( String s , String t) {
int n = s . length ();
int m = t . length ();
if ( Math . abs (n - m) > 1 ) return false ;
for ( int i = 0 ; i < Math . min (m , n); i ++ ){
if ( s . charAt (i) != t . charAt (i)){
if (n == m) return s . substring (i + 1 ) . equals ( t . substring (i + 1 ));
if (n > m) return s . substring (i + 1 ) . equals ( t . substring (i));
if (n < m) return s . substring (i) . equals ( t . substring (i + 1 ));
}
}
return Math . abs (n - m) == 1 ;
}
} 结合上一道题的错误来看，可以很容易看到只依靠 LCS 长度解决这道题的乏力；因为 LCS 长度和 edit distance 对字符串结构的利用是不一样的，mismatch 的字符可以出现错位，而 edit distance 不支持一次操作进行修正。算法导论上也写的非常清楚，鉴定两条 DNA 序列的相似度，substring 是一种思路（KMP），LCS是一种思路，而 edit distance 是另一种思路。
然而相同的是，这道题思考并寻找 optimal substructure 的思路是非常接近的，都是直接从最终答案 String Z 的结构 top-down 往回看。因为对于每个 string，我们对其任意操作都会构造出来一个只与它自己相差一个字符的新 string.
Z[1,2...k] 为最少修改之后的 String Z;
注意这里 Z 可以有多个正解，因为可以有多个最优的正确操作。
于是；
若 S[n] == T[m] ，则Z[1,2.. k - 1] 为 S[n - 1] 和 T[m - 1] 的解；
若 S[n] != T[m]:
最优解为 S[1,2 ..n] 与 T[1,2 .. m - 1] 构造而成，
最优解为 S[1,2 .. n - 1] 与 T[1,2 .. m] 构造而成
最优解为 S[1,2 .. n - 1] 和 T[1,2 .. m - 1] 构造而成
直接把 S[n] 和 T[m] replace 成一样的。
来自 Stanford 课件，bottom - up 的 String 构造法。我们定义 D(i, j - 1) 为 insertion 是因为 i 是外循环位置，j 是内循环位置；因此当 i 固定，相对于 j 取了前一个位置 + 新字符的时候是 j 的 insertion； 而 D(i - 1, j) 代表 j 在新循环中并没有增加长度，反而从 i 里删除了。
考虑到所有操作都在双循环内完成，调换循环位置并不会影响算法正确性，但是会赋予每次操作相反的意义，即调换等价互补操作 "S + 1" 和 "T - 1".
其实和算法导论的图是一个意思，方向不同而已。
如果这题每种操作附带了 cost ，要求最小的 cost 怎么办？
不难看出，add 和 delete 作为互补操作，其 cost 是一样的；即使不一样，我们也可以在两个 String 的构造过程中，总是选择更小的那个。
Copy public class Solution {
public int minDistance ( String word1 , String word2) {
int n = word1 . length ();
int m = word2 . length ();
int [][] dp = new int [n + 1 ][m + 1 ];
for ( int i = 1 ; i <= n; i ++ ){
dp[i][ 0 ] = i;
}
for ( int i = 1 ; i <= m; i ++ ){
dp[ 0 ][i] = i;
}
for ( int i = 1 ; i <= n; i ++ ){
for ( int j = 1 ; j <= m; j ++ ){
if ( word1 . charAt (i - 1 ) == word2 . charAt (j - 1 )){
// 注意这步考虑 dp[i - 1][j - 1]同时再考虑
// min(dp[i - 1][j], dp[i][j - 1]) + 1 也合乎逻辑，一样可以 AC
dp[i][j] = dp[i - 1 ][j - 1 ];
} else {
dp[i][j] = Math . min (dp[i - 1 ][j - 1 ] ,
Math . min (dp[i - 1 ][j] ,
dp[i][j - 1 ])) + 1 ;
}
}
}
return dp[n][m];
}
} (Google, Snapchat面经)
和 Edit distance 非常像，考虑到 add/delete 在构造 string 上的等价性质，问题的 optimal substructure 即为
dp[i][j] = substring(i,j) 范围内，构造 palindrome 的最小编辑次数
如果 s[i] == s[j]
dp[i][j] = dp[i + 1][j - 1] (不需要操作)
如果 s[i] != s[j]，那么我们可以经 add/delete 操作构造出当前的 s(i, j)
注意这题不支持 replace，如果支持的话，dp[i][j] 还要看一个新状态，dp[i + 1][j - 1]
Copy public class Main {
private static int minEditDistance ( String str){
if (str == null || str . length () <= 1 ) return 0 ;
int n = str . length ();
// dp[i, j] = min edit distance for substring (i , j);
int [][] dp = new int [n][n];
for ( int i = 1 ; i < n; i ++ ){
for ( int j = i; j >= 0 ; j -- ){
if (j == i) {
dp[j][i] = dp[i][j] = 0 ;
} else {
if ( str . charAt (i) == str . charAt (j)){
dp[j][i] = dp[i][j] = (j + 1 == i) ? 0
: dp[j + 1 ][i - 1 ];
} else {
dp[j][i] = dp[i][j] = (j + 1 == i) ? 1
: Math . min (dp[j + 1 ][i] , dp[j][i - 1 ]) + 1 ;
}
}
}
}
return dp[ 0 ][n - 1 ];
}
public static void main ( String [] args){
System . out . println ( minEditDistance( "geekforgeeks" ) );
}
} Hard 难度题，字符串 DP.
首先我们可以观察到最终结果只需要返回 true / false ，而不是很在乎具体到哪个位置的时候 wildcard 匹配了什么字符，所以是一个用 DP 的信号。
顺着这个思路想，这题具有这章其他 DP 类问题都非常相似的结构和 optimal substructure ，即都是 1 / 2 个 string 从小往大“生长”，每一步需要做 match 的判断构造出更长 string 的正解；以这题的结构，不难想出 dp 的数组结构就是 dp[i][j] 代表 s 的前 i 个字符串能否和 p 的前 j 个字符串成功匹配，以 dp[n][m] 为最终解。
剩下的问题就是，如何正确识别所有情况。
s[i] , p[j] 为 s , p 的第 i / j 个字符，略去 off-by-one 的 index 问题
当 p[j] = 常规字母时；
如果 s[i] == p[j]，当前位置 match;
同时如果之前的字符串 dp[i - 1][j - 1] 也 match ，则 dp[i][j] match;
当 p[j] 为 '?' 时；
当前位置一定 match，只看 dp[i - 1][j - 1] 是否也 match;
当 p[j] 为 '*' 时；
只 match 当前一个字符，看 dp[i - 1][j - 1];
LeetCode 测试了下，其实这行拿掉也是正确的
不 match 任何字符，看 dp[i][j - 1] (忽略 p[j] 的存在)
match 多个字符，看 dp[i - 1][j]
注意这里由于循环结构的关系，其实对于每一个 j ，我们会去考虑 [0 , i-1] 所有的可能性，所以可以用一个状态指代所有前面的 match.
最后要注意一下 dp[0][0], dp[0][i] 的初始化。
Copy public boolean isMatch( String s , String p) {
if (s == null || p == null ) return false ;
int n = s . length ();
int m = p . length ();
boolean [][] dp = new boolean [n + 1 ][m + 1 ];
dp[ 0 ][ 0 ] = true ;
for ( int i = 1 ; i <= m; i ++ ){
if ( p . charAt (i - 1 ) == '*' ) dp[ 0 ][i] = true ;
else break ;
}
for ( int i = 1 ; i <= n; i ++ ){
for ( int j = 1 ; j <= m; j ++ ){
if ( p . charAt (j - 1 ) == '?' ||
s . charAt (i - 1 ) == p . charAt (j - 1 )){
dp[i][j] = dp[i - 1 ][j - 1 ];
} else if ( p . charAt (j - 1 ) == '*' ){
dp[i][j] = dp[i - 1 ][j] || dp[i][j - 1 ];
}
}
}
return dp[n][m];
} 也是 Hard 题，长得还和 Wildcard Matching 特别像。
最大的不同是，在这里 '*' 号是和其前一个字符有联系的，和其前一个字符一起，代表着“多个或0个星号前面的字符”。 这里我们需要假设 p 不会以星号开始，也不会有连续多个星号出现，不然现有题意描述是无法解决这些问题的。
遇到常规字母和 '.' 的处理和上一题没有任何区别；
遇到 p[j] 为星号时：
如果 p[j - 1] 是 '.', 那么这个星号
dp[i - 1][j] 以当前星号匹配一个或多个多个字符；
dp[i][j - 1] 只让 p[j - 1] 匹配，当前星号不匹配字符；
否则，星号位置能否匹配取决于 dp[i][j - 2]，即让(p[j - 1] + 当前星号)都不匹配任何字符。
以这两道题看，dp[i - 1][j] 都代表着 “以 p 当前 * 字符，匹配 s 的[1,n]长度字符”
这题dp[0][i]初始化和 Wildcard 不太一样，因为会有 c*a*b 这种情况，多个星号跳着出现，不要立刻 break 掉，而要扫到底，dp[0][i] 要看 dp[0][i - 2];
Copy public boolean isMatch( String s , String p) {
if (s == null || p == null ) return false ;
int n = s . length ();
int m = p . length ();
boolean [][] dp = new boolean [n + 1 ][m + 1 ];
dp[ 0 ][ 0 ] = true ;
for ( int i = 2 ; i <= m; i ++ ){
if ( p . charAt (i - 1 ) == '*' ) dp[ 0 ][i] = dp[ 0 ][i - 2 ];
}
for ( int i = 1 ; i <= n; i ++ ){
for ( int j = 1 ; j <= m; j ++ ){
char chars = s . charAt (i - 1 );
char charp = p . charAt (j - 1 );
if (charp == '.' || charp == chars){
dp[i][j] = dp[i - 1 ][j - 1 ];
} else if (charp == '*' ){
char charPrev = p . charAt (j - 2 );
if (charPrev == '.' || charPrev == chars){
dp[i][j] = dp[i - 1 ][j] || dp[i][j - 2 ] || dp[i][j - 1 ];
} else {
dp[i][j] = dp[i][j - 2 ];
}
}
}
}
return dp[n][m];
} 这是一道很像 rod-cutting 还有 palindrome paritioning 的题，利用的结构也一样。
要保证算法的正确性，我们要迭代考虑题目中所有的 substring 组合，不然可能会漏掉正解。考虑到题目可能的 substring 数量，这题的时间复杂度至少为 O(n^2)，因此我们能做的就是利用好 substring 相互覆盖的地方避免重复计算。
Copy public class Solution {
public boolean wordBreak ( String s , Set < String > wordDict) {
int n = s . length ();
boolean [][] canBreak = new boolean [n][n];
for ( int i = 0 ; i < n; i ++ ){
for ( int j = i; j >= 0 ; j -- ){
String str = s . substring (j , i + 1 );
if ( wordDict . contains (str)) canBreak[i][j] = canBreak[j][i] = true ;
if (j > 0 && canBreak[j][i] && canBreak[ 0 ][j - 1 ]) canBreak[ 0 ][i] = canBreak[i][ 0 ] = true ;
}
}
return canBreak[ 0 ][n - 1 ];
}
} 在如上代码 AC 之后，思考之后可以发现两个很明显的优化：
optimal substructure 是，如果 [0, j] 可以 break 并且 [j + i , i] 在字典里，那么 [0 , j] 就可以 break.
我们不需要存储所有区间是否可以 break，只取从 index = 0 开始到 i 为止是否可以就行了；空间优化成了 O(n);
因此如果回头扫到了当前位置可以 break 的时候，我们就可以做 early termination.
同时对于每个考虑的中间位置 j ，如果在 j 上不能 break，那么取 substring 和检查字典的必要都没有。
Copy public boolean wordBreak( String s , Set< String > wordDict) {
int n = s . length ();
boolean [] canBreak = new boolean [n + 1 ];
canBreak[ 0 ] = true ;
for ( int j = 1 ; j <= n; j ++ ){
for ( int i = j; i >= 0 ; i -- ){
if ( ! canBreak[i]) continue ;
String str = s . substring (i , j);
if ( wordDict . contains (str)) canBreak[j] = true ;
}
}
return canBreak[n];
} 这题有简单暴力的 dfs + backtracking，然而为了优化计算时间，也要利用备忘录法和记忆化搜索。
这题做出来容易，AC 有点难，因为用时卡的厉害，有坑爹的 test case :
【s ="aaaaaaaaaaaaaaaaa...aaaa" , dict = "a", "aa", "aaa", "aaaa"】
硬搜的时间复杂度为 O(2^n)，搜索树结构见算法导论的 rod-cutting.
最容易想到的几种优化方式：
预处理，建 boolean[][] 表示所有可能区间内是不是 word，方便dfs 时判断要不要进入下一层循环；
记录字典里最长单词长度作为 step size，dfs 每次循环寻找位置时限制最远的搜素距离；（用于优化 s 相对于 word 非常长的情况）
然而单独靠以上两种优化都还不够。。
https://leetcode.com/discuss/80266/java-dfs-memoization-dfs-and-pruning-solutions-with-analysis
事实证明在这题里，直接用 HashSet + substring 检查字典，要比预处理计算 boolean[][] 快。 (8ms vs. 22ms)
O(len(wordDict) ^ len(s / minWordLenInDict))
Because there're len(wordDict) possibilities for each cut，同时空间占用可能会比较大。
Copy public class Solution {
public List < String > wordBreak ( String s , Set < String > wordDict) {
int n = s . length ();
boolean [][] isWord = new boolean [n][n];
int maxLength = 0 ;
for ( String str : wordDict){
maxLength = Math . max (maxLength , str . length ());
}
return dfs(s , wordDict , new HashMap < Integer , List < String >>() , 0 , maxLength) ;
}
private List<String> dfs(String s, Set<String> wordDict, HashMap<Integer, List<String>> map, int start, int maxLength){
if (map.containsKey(start)) return map. get (start);
List < String > rst = new ArrayList < String >();
if (start >= s.length()) rst. add ( "" );
for ( int i = start; i - start <= maxLength && i < s . length (); i ++){
String str = s . substring (start , i + 1 );
if ( wordDict . contains (str)){
List < String > afterWards = dfs(s , wordDict , map , i + 1 , maxLength) ;
for ( String next : afterWards){
if (i + 1 < s . length ()) rst . add (str + " " + next);
else rst . add (str);
}
}
}
map . put (start , rst);
return rst ;
}
} 首先从题目结构来看，和这章的前几道字符串 DP 非常相似，都是一个字符串 “构造问题”，即用小的 substring 通过生长和拼接，构造出更大的目标 string. 一般这类问题有天然的 bottom-up 思路，当然，top-bottom 的递归思路也是完全可行的。
首先贴一个自己写的暴力解法，三维 dp，dp[i][j][k] 代表着“s1 的前 i 个字符和 s2 的前 j 个字符，能否构造成 s3 的前 k 个字符”。
下面代码时间复杂度 O(s1.len * s2.len * s3.len)，可以 AC，但是显然还有优化的空间。
Copy public class Solution {
public boolean isInterleave ( String s1 , String s2 , String s3) {
if (s1 == null || s2 == null || s3 == null ) return false ;
if ( s3 . length () != s1 . length () + s2 . length ()) return false ;
if ( s1 . length () == 0 ) return s2 . equals (s3);
if ( s2 . length () == 0 ) return s1 . equals (s3);
int s1Len = s1 . length ();
int s2Len = s2 . length ();
int s3Len = s3 . length ();
// dp[i][j][k] if the first i chars from s1 and first j chars from s2
// can interleave to produce first k chars of s3
boolean [][][] dp = new boolean [s1Len + 1 ][s2Len + 1 ][s3Len + 1 ];
dp[ 0 ][ 0 ][ 0 ] = true ;
for ( int k = 1 ; k <= s3Len; k ++ ){
char char3 = s3 . charAt (k - 1 );
for ( int i = 1 ; i <= k && i <= s1Len; i ++ ){
char char1 = s1 . charAt (i - 1 );
for ( int j = 1 ; j <= k && j <= s2Len; j ++ ){
char char2 = s2 . charAt (j - 1 );
if (char1 == char3 && k - i >= 0 && k - i <= s2Len && dp[i - 1 ][k - i][k - 1 ]) {
dp[i][k - i][k] = true ;
}
if (char2 == char3 && k - j >= 0 && k - j <= s1Len && dp[k - j][j - 1 ][k - 1 ]) {
dp[k - j][j][k] = true ;
}
}
}
}
return dp[s1Len][s2Len][s3Len];
}
} 简单观察之后发现正确答案的限制条件： k = i + j，换句话说，k 可以用 i + j 表示出来，因此不需要以 k 作为单独维度遍历。
同时我们也要处理好 i = 0 和 j = 0 的初始化条件。
时间空间复杂度 O(s1.len * s2.len)
Copy public class Solution {
public boolean isInterleave ( String s1 , String s2 , String s3) {
if (s1 == null || s2 == null || s3 == null ) return false ;
if ( s3 . length () != s1 . length () + s2 . length ()) return false ;
if ( s1 . length () == 0 ) return s2 . equals (s3);
if ( s2 . length () == 0 ) return s1 . equals (s3);
int s1Len = s1 . length ();
int s2Len = s2 . length ();
// dp[i][j][k] if the first i chars from s1 and first j chars from s2
// can interleave to produce first i + j chars of s3
boolean [][] dp = new boolean [s1Len + 1 ][s2Len + 1 ];
dp[ 0 ][ 0 ] = true ;
for ( int i = 0 ; i < s1Len; i ++ ){
if ( s1 . charAt (i) == s3 . charAt (i) && dp[i][ 0 ]) dp[i + 1 ][ 0 ] = true ;
}
for ( int i = 0 ; i < s2Len; i ++ ){
if ( s2 . charAt (i) == s3 . charAt (i) && dp[ 0 ][i]) dp[ 0 ][i + 1 ] = true ;
}
for ( int i = 1 ; i <= s1Len; i ++ ){
for ( int j = 1 ; j <= s2Len; j ++ ){
char char1 = s1 . charAt (i - 1 );
char char2 = s2 . charAt (j - 1 );
char char3 = s3 . charAt (i + j - 1 );
if (char1 == char3 && dp[i - 1 ][j]) dp[i][j] = true ;
if (char2 == char3 && dp[i][j - 1 ]) dp[i][j] = true ;
}
}
return dp[s1Len][s2Len];
}
} 
