2-7-2018 String DP

两个String放一起，从某个位置开始看看是否match;要是不match了，就得错开一位看;要是match了，就都往后挪一位看。在Edit Distance里面，稍微特殊一点，因为我们还有一个replace操作，可以直接修正当前mismatch，让两个字符串都挪动一格位置。

于是对于每一个String，就有了一个对于其位置敏感的维度dp[i]，代表从最左面开始的i个字符构成的字符串，也是子问题的结构定义。因为我们有两个String并且需要枚举位置之间可能的各种交错穿插，我们就需要两个维度dp[i][j]，代表第一个字符串中的i个字符和第二个字符串中的j个字符匹配情况。

Longest Common Subsequence

给定长度为m的字符串{1,2,3...m}，其subsequences的数量总数为2^m，即对每个字符选择“取/不取”。

如果A的字符与B的字符不match，则我们要看只取A字符情况下的LCS和只取B字符情况下LCS的较大值。
如果A的字符与B的字符match，则我们则是看在不取该字符情况下LCS + 1。

public class Solution {
    /*
     * @param A: A string
     * @param B: A string
     * @return: The length of longest common subsequence of A and B
     */
    public int longestCommonSubsequence(String A, String B) {
        // write your code here
        int n = A.length();
        int m = B.length();

        int[][] dp = new int[n + 1][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][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n][m];
    }
}

related problems: Longest Common Substring,

Longest Common Substring

如果match，我就+1，如果不match，我就直接set 0.

public class Solution {
    public int longestCommonSubstring(String A, String B) {
        // write your code here
        if (A == null || B == null) return 0;

        int m = A.length(), n = B.length();

        // A B C D 
        // C B C E 
        // dp[i][j] = dp[i-1][j-1] + 1      if A[i] == B[j]
        //          = 0                     if A[i] != B[j]
        // return max 
        int[][] dp = new int[m + 1][n + 1];
        int max = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (A.charAt(i - 1) != B.charAt(j - 1)) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        return max;
    }
}

longest common prefix

note that, 这道题本身不难，但是需要考虑全面一些conner case。比如说，String array中存在空字符的情况： ["abc","abcd","","ab","ac"]，需要特别注意。

public String longestCommonPrefix(String[] strs) {
    // write your code here
    if (strs == null || strs.length == 0) return "";

    int num = 0;

    for (int i = 0; i < strs.length; ++i) {
        if (strs[i].length() == 0) return "";
    }

    for (int i = 0; i < strs[0].length(); ++i) {
        char c = strs[0].charAt(i);
        for (int j = 1; j < strs.length; ++j) {
            if (strs[j].length() < i || strs[j].charAt(i) != c) {
                return strs[0].substring(0, num);
            }
        }
        num++;
    }
    return strs[0].substring(0, num);
}

对于这道题，我们无法用LCS长度来解决，因为LCS长度和edit distance对字符串结构的利用是不一样的。LCS中mismatch的字符可以出现错位，而edit distance出现要进行修正。算法导论上写的非常清楚，鉴定两条DNA序列的相似度，substring是一种思路(KMP), LCS是一种思路，而edit distance是另一种思路。refer to slides, by Stanford因为对于每个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成一样的。

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][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];
    }
}

one edit distance

basic idea is that 既然有且只有1个位置mismatch，我们可以直接在找到mismatch位置上再判断。

让n，m为两个String的长度
- 如果m == n，mismatch之后的子字符串一定完全相等; => replace operation
- 否则长的那段在i之后的substring一定与短的以i开始的substring全等; => delete or insert operation
- 如果在循环末尾还没有发现mismatch，两个字符串末尾必然会有1的长度差，否则S == T. => may exist length diff by 1

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(n, m); ++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;
    }
}

匹配类DP

2-7-2018 String DP

Longest Common Subsequence

Longest Common Substring

longest common prefix

Edit Distance

one edit distance

results matching ""

No results matching ""