# Maximum Length of Repeated Subarray & Edit Distance

Dec 24, 2019

dp[i, j] = \left{ \begin{aligned} 0 &, & A[i] \neq B[i] \ dp[i-1, j-1] + 1 &, & A[i] = B[i] \end{aligned} \right.

int findLength(vector<int>& A, vector<int>& B) {
int n = A.size();
if (n == 0) return 0;

vector<int> dp(n+1, 0);
int res = 0;
for(int i = 1;i <= n; i++) {
for(int j = n;j >= 1; j--) {
dp[j] = (A[i-1] == B[j-1]) ? (dp[j-1] + 1) : 0;
res = max(dp[j], res);
}
}

return res;
}


• 插入
• 删除
• 替换

dp[i, j]word1[0..i]word2[0..j]的编辑距离：

• 如果word1[i] == word2[j]的话，dp[i,j] = dp[i-1, j-1]，即不需要做任何编辑
• 如果word1[i] != word2[j]的话，我们可以尝试删除或替换两种操作
• 删除word1[i]
• 删除word2[i]
• 替换word1[i]word2[i]

dp[i, j] = min(dp[i-1, j], dp[i, j-1], dp[i-1, j-1])

dp[i, j] = \left{ \begin{aligned} i &, & i = 0 \ j &, & j = 0 \ dp[i-1, j-1] &, & word1[i] = word2[j] \ min(dp[i-1, j], dp[i, j-1], dp[i-1, j-1]) &, & A[i] \neq B[i] \end{aligned} \right.

int minDistance(string word1, string word2) {
int n1 = word1.size(), n2 = word2.size();
vector<int> dp(n2 + 1);
for(int j = 0;j <= n2; j++) {
dp[j] = j;
}
int prev;
for(int i = 1; i <= n1; i++) {
prev = dp[0];
dp[0] = i;
for(int j = 1;j <= n2; j++) {
swap(dp[j], prev);
if (word1[i-1] != word2[j-1]) {
dp[j] = min(min(dp[j-1], dp[j]), prev) + 1;
}
}
}
return dp[n2];
}

LeetCodeLeetCode

Maximum Level Sum of a Binary Tree

Flipping an Image