7/2, 动态规划，字符串类
字符串 DP 类的很多典型问题，用这一张图都能说明白：
两个 String 放一起，从某个位置开始看看是否 match; 要是不 match 了，就得错开一位看；要是 match 了，就都往后挪一位看。在 Edit Distance 里面，稍微特殊一点，因为我们还有一个 replace 操作，可以直接修正当前 mismatch，让两个字符串都挪动一格位置。
于是对于每一个 String，就有了一个对于其位置敏感的维度 dp[i]，代表从最左面开始的 i 个字符构成的字符串，也是子问题的结构定义。因为我们有两个 String 并且需要枚举位置之间可能的各种交错穿插，我们就需要两个维度 dp[i][j]，代表第一个字符串中的 i 个字符和第二个字符串中的 j 个字符匹配情况。
Longest Common Subsequence(CLRS)
研究一个新问题时，最好还是从算法导论开始。
给定长度为 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[][] 的最右下角。
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];
}
}
One Edit Distance
一开始未经思考尝试以 LCS 长度判断，但是这个思路是错的，因为 S 和 T 的 LCS 长度可以满足条件，但是 mismatch 的字符却不一定是在同一个位置。况且， LCS 的时间复杂度是 O(mn), 这题应该很明显有 O(n) 的解法。
正解借鉴了论坛的代码，其实非常简洁。
核心思想是，既然有且只有 1 个位置 mismatch，我们可以直接在找到 mismatch 位置上判断：
让 n, m 为两个 String 的长度
如果 m == n ，mismatch 之后的子字符串一定完全相等；
否则长的那段在 i 之后的 substring 一定与短的以 i 开始的 substring 全等；
如果在循环末尾还没有发现 mismatch，两个字符串末尾必然会有 1 的长度差，否则 S == T.
在字符串 DP 中，原始字符串上的 substring，等价于原始区间内的 subproblem.
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;
}
}
Edit Distance
结合上一道题的错误来看，可以很容易看到只依靠 LCS 长度解决这道题的乏力；因为 LCS 长度和 edit distance 对字符串结构的利用是不一样的，mismatch 的字符可以出现错位，而 edit distance 不支持一次操作进行修正。算法导论上也写的非常清楚，鉴定两条 DNA 序列的相似度，substring 是一种思路（KMP），LCS是一种思路，而 edit distance 是另一种思路。
关于这个问题最好的slides, by Stanford
然而相同的是，这道题思考并寻找 optimal substructure 的思路是非常接近的，都是直接从最终答案 String Z 的结构 top-down 往回看。因为对于每个 string，我们对其任意操作都会构造出来一个只与它自己相差一个字符的新 string.
S[1,2,3..n] 为 String S;
T[1,2,3..m] 为 String T;
Z[1,2...k] 为最少修改之后的 String Z;
注意这里 Z 可以有多个正解，因为可以有多个最优的正确操作。
类似于 LCS，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[n]
OR 增加 T[m];
最优解为 S[1,2 .. n - 1] 与 T[1,2 .. m] 构造而成
删掉 T[m]
OR 增加 T[n];
最优解为 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 的构造过程中，总是选择更小的那个。
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面经)
Delete Operation for Two Strings 7/1
很久没看，纠结在同时允许删除两个String的元素怎么dp。复习完edit distance，迅速开窍，在字符串2删除实际上就是在字符串1里面插入，和edit distance一样，一次AC。
public class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length(); int n=word2.length();
int[][] dp = new int[m+1][n+1];
for(int[] d :dp) Arrays.fill(d, Integer.MAX_VALUE);
for(int i=0;i<=m;i++)
dp[i][0] = i;
for(int j=0;j<=n;j++)
dp[0][j] = j;
dp[0][0] = 0;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++){
if(word1.charAt(i-1)==word2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else{
dp[i][j] = Math.min(dp[i][j], dp[i][j-1]+1);
dp[i][j] = Math.min(dp[i][j], dp[i-1][j]+1);
}
}
return dp[m][n];
}
}
Minimum insertions to form a palindrome
和 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] (不需要操作)
同时考虑 i , j 相邻的情况
如果 s[i] != s[j]，那么我们可以经 add/delete 操作构造出当前的 s(i, j)
s(i + 1, j) + ADD
s(i, j - 1) + ADD
注意这题不支持 replace，如果支持的话，dp[i][j] 还要看一个新状态，dp[i + 1][j - 1]
public class PalindromeInsert {
public static int getCost(String s){
int len = s.length();
int[][] dp = new int[len][len];
char[] arr = s.toCharArray();
for(int i=0;i<len;i++){
dp[i][i] = 0;
if(i<len-1){
if(arr[i]==arr[i+1]) dp[i][i+1] = 0;
else dp[i][i+1] = 1;
}
}
for(int l=3;l<=len;l++)
for(int i=0;i+l-1<len;i++){
if(arr[i]==arr[i+l-1])
dp[i][i+l-1] = dp[i+1][i+l-2];
else
dp[i][i+l-1] = Math.min(dp[i+1][i+l-1], dp[i][i+l-2])+1;
}
return dp[0][len-1];
}
public static void main(String[] args){
String s = "geeks";
int cost = getCost(s);
System.out.println(cost);
}
}
WildCard Matching
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] 的初始化。
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];
}
Regular Expression Mathcing
也是 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] 同下。
否则，星号位置能否匹配取决于 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];
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
boolean[][] dp = new boolean[s.length()+1][p.length()+1];
dp[0][0] = true;
for (int i = 0; i < p.length(); i++) {
if (p.charAt(i) == '*' && dp[0][i-1]) {
dp[0][i+1] = true;
}
}
for (int i = 0 ; i < s.length(); i++) {
for (int j = 0; j < p.length(); j++) {
if (p.charAt(j) == '.') {
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == s.charAt(i)) {
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == '*') {
if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
dp[i+1][j+1] = dp[i+1][j-1];
} else {
dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
/*
If p.charAt(j) == '*':
here are two sub conditions:
1 if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2] //in this case, a* only counts as empty
2 if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
dp[i][j] = dp[i-1][j] //in this case, a* counts as multiple a
or dp[i][j] = dp[i][j-1] // in this case, a* counts as single a
or dp[i][j] = dp[i][j-2] // in this case, a* counts as empty
*/
}
}
}
}
return dp[s.length()][p.length()];
}
递归
public boolean isMatch(String s, String p) {
if(p.length()==0)
return s.length()==0;
if(p.length()==1)
return (s.length()==1 && (s.charAt(0)==p.charAt(0)||p.charAt(0)=='.'));
if(p.charAt(1)=='*'){
if(isMatch(s, p.substring(2)))
return true;
else if(s.length()>0 && (s.charAt(0)==p.charAt(0)||p.charAt(0)=='.'))
return isMatch(s.substring(1), p);
}
if(s.length()>0 && (s.charAt(0)==p.charAt(0)||p.charAt(0)=='.'))
return isMatch(s.substring(1),p.substring(1));
return false;
}
Word Break
这是一道很像 rod-cutting 还有 palindrome paritioning 的题，利用的结构也一样。
要保证算法的正确性，我们要迭代考虑题目中所有的 substring 组合，不然可能会漏掉正解。考虑到题目可能的 substring 数量，这题的时间复杂度至少为 O(n^2)，因此我们能做的就是利用好 substring 相互覆盖的地方避免重复计算。
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 和检查字典的必要都没有。
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
if(s==null || s.length()==0) return true;
int n = s.length();
boolean[] dp= new boolean[n+1]; Arrays.fill(dp, false);dp[0] = true;
for(int i=1;i<=n;i++){
for(String word : wordDict){
if(i-word.length()<0) continue;
if(word.equals(s.substring(i-word.length(),i)))
dp[i] = dp[i] || dp[i-word.length()];
}
}
return dp[n];
}
}
Word Break II
这题有简单暴力的 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，同时空间占用可能会比较大。
public class Solution {
HashMap<String, List<String>> map = new HashMap<String, List<String>>\(\);
public List<String> wordBreak\(String s, List<String> wordDict\) {
return dfs\(s, wordDict\);
}
public List<String> dfs\(String s, List<String> wordDict\){
if\(map.containsKey\(s\)\) return map.get\(s\);
ArrayList<String> cur = new ArrayList<String>\(\);
if\(s.length\(\)==0\){
cur.add\(""\);
return cur;
}
for\(String word : wordDict\){
if\(s.startsWith\(word\)\){
List<String> sublist = dfs\(s.substring\(word.length\(\)\), wordDict\);
for\(String sub : sublist\){
cur.add\(word + \(sub.length\(\)==0?"":" "\) +sub\);
}
}
}
map.put\(s, cur\);
return cur;
}
}
Interleaving String
首先从题目结构来看，和这章的前几道字符串 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，但是显然还有优化的空间。
简单观察之后发现正确答案的限制条件： k = i + j，换句话说，k 可以用 i + j 表示出来，因此不需要以 k 作为单独维度遍历。
同时我们也要处理好 i = 0 和 j = 0 的初始化条件。
时间空间复杂度 O(s1.len * s2.len)
自己写的时候用了S3和S1下标i j做dp,这样 s2下标是i-j. 不方便使用
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];
}
}
Student Attendance Record II
先用DFS剪支，length 13的时候超时。
public class Solution {
int count =0;
public int checkRecord(int n) {
dfs(n, new StringBuilder());
return count;
}
public void dfs(int n, StringBuilder sb){
if(!isR(sb.toString())) return;
if(sb.length()==n && isR(sb.toString())){
count++;return;
}
char[] arr = new char[]{'A','L','P'};
for(int i=0;i<arr.length;i++){
sb.append(arr[i]);
dfs(n, sb);
sb.deleteCharAt(sb.length()-1);
}
}
public boolean isR(String s){
return !s.matches(".*LLL.*") && !s.matches(".*A.*A.*");
}
}
DFS不行，上DP。纠结在怎么表示连续的L，写了几个式子后觉得都太繁琐，似对似错。论坛解法
dp[i][j][k]表示i个字符，最多(at most)有j个‘A’，k个‘L’，这个比较好想。dp[i]与dp[i-1]的关系如何递推，需要琢磨。这里可以看出，dp[i-1][j-1][k-1] 和dp[i-1][j][k] 是被包含与包含的关系，状态不独立。常见的dp状态都是独立的，不独立时会采用local(以当前字符结尾) global(不一定以当前字符结尾)。而这道题巧就巧在可以dp。
dp[i-1][j][k] 后面接'P'，可以形成dp[i][j][k];
dp[i-1][j-1][k] 后面接‘A’，可以形成dp[i][j][k];
dp[i-1][j][k－1] 后面接‘L’，可以形成dp[i][j][k];
诚然dp[i-1][j][k－1] 和dp[i-1][j][k] 有overlap，然而后面接了不同的字符，dp[i][j][k]没有重复计算(overcount)
public class Solution {
public int checkRecord(int n) {
int MOD = 1000000007;
int[][][] dp = new int[n+1][2][3];
dp[0] = new int[][]{ {1,1,1},{1,1,1}};
for(int i=1;i<=n;i++)
for(int j=0;j<2;j++)
for(int k=0;k<3;k++){
int val = dp[i - 1][j][2]; // ...P
if (j > 0) val = (val + dp[i - 1][j - 1][2]) % MOD; // ...A
if (k > 0) val = (val + dp[i - 1][j][k - 1]) % MOD; // ...L
dp[i][j][k] = val;
}
return dp[n][1][2];
}
}