Longest Common Subsequence

Given two strings, find the longest common subsequence (LCS).

Your code should return the length of LCS.

Example

For "ABCD" and "EDCA", the LCS is "A" (or "D", "C"), return 1.

For "ABCD" and "EACB", the LCS is "AC", return 2.

Clarification

What’s the definition of Longest Common Subsequence?

Solution: Dynamic Programming

public int longestCommonSubsequence(String A, String B) {
    if (A == null || A.length() == 0 || B == null || B.length() == 0) {
        return 0;
    }
    int[][] lcs = new int[A.length()][B.length()];
    for (int i = 0; i < A.length(); i++) {
        for (int j = 0; j < B.length(); j++) {
            if (i == 0 || j == 0) {
                lcs[i][j] = A.charAt(i) == B.charAt(j) ? 1 : 0;
            } else {
                if (A.charAt(i) == B.charAt(j)) {
                    lcs[i][j] = lcs[i - 1][j - 1] + 1;
                } else {
                    lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);
                }
            }
        }
    }
    return lcs[A.length() - 1][B.length() - 1];
}
FacebookTwitterGoogle+Share

Longest Common Substring

Given two strings, find the longest common substring.

Return the length of it.

Example
Given A = “ABCD”, B = “CBCE”, return 2.

Note
The characters in substring should occur continuously in original string. This is different with subsequence.

Challenge
O(n x m) time and memory.

Solution: Dynamic Programming

public int longestCommonSubstring(String A, String B) {
    int[][] lcs = new int[A.length()][B.length()];
    int max = 0;
    for (int i = 0; i < A.length(); i++) {
        for (int j = 0; j < B.length(); j++) {
            if (A.charAt(i) == B.charAt(j)) {
                if (i == 0 || j == 0) {
                    lcs[i][j] = 1;
                } else {
                    lcs[i][j] = lcs[i - 1][j - 1] + 1;
                }
            }
            if (lcs[i][j] > max) {
                max = lcs[i][j];
            }
        }
    }
    return max;
}

Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE"while "AEC" is not).

Example

Given S = "rabbbit", T = "rabbit", return 3.

Challenge

Do it in O(n2) time and O(n) memory.

O(n2) memory is also acceptable if you do not know how to optimize memory.

Solution: Dynamic Programming

Version 1. O(m*n)time O(m*n)space
f[i][j] means the number of different ways to select first j chars of T from first i chars from S, 即从S的前i个字符中挑出T的前j个字符 有多少种方案
f[i][j] = f[i-1][j-1] + f[i-1][j] //S[i]=T[j]
= f[i-1][j] //S[i]!=T[j]

public int numDistinct(String S, String T) {
    //f[i][j] means the number of different ways to select first j chars of T from first i chars from S
    //从S的前i个字符中挑出T的前j个字符 有多少种方案
    //f[i][j] = f[i-1][j-1] + f[i-1][j] //S[i]=T[j]
    //      = f[i-1][j] //S[i]!=T[j]
    if (S == null || T == null || S.length() < T.length()) {
        return 0;
    }
    int[][] numDistinct = new int[S.length() + 1][T.length() + 1];
    for (int i = 0; i <= S.length(); i++) {
        numDistinct[i][0] = 1;
    }
    for (int i = 1; i <= S.length(); i++) {
        for (int j = 1; j <= i && j <= T.length(); j++) {
            if (S.charAt(i - 1) == T.charAt(j - 1)) {
                numDistinct[i][j] = numDistinct[i - 1][j - 1] + numDistinct[i - 1][j];
            } else {
                numDistinct[i][j] = numDistinct[i - 1][j];
            }
        }
    }
    return numDistinct[S.length()][T.length()];
}

Version 2. O(m*n) time, O(n)space

just mod 2 for the row index. Rolling array.

public int numDistinct(String S, String T) {
    if (S == null || T == null || S.length() < T.length()) {
        return 0;
    }
    int[][] numDistinct = new int[2][T.length() + 1];
    for (int i = 0; i < 2; i++) {
        numDistinct[i][0] = 1;
    }
    for (int i = 1; i <= S.length(); i++) {
        for (int j = 1; j <= i && j <= T.length(); j++) {
            if (S.charAt(i - 1) == T.charAt(j - 1)) {
                numDistinct[i % 2][j] = numDistinct[(i - 1) % 2][j - 1] + numDistinct[(i - 1) % 2][j];
            } else {
                numDistinct[i % 2][j] = numDistinct[(i - 1) % 2][j];
            }
        }
    }
    return numDistinct[S.length() % 2][T.length()];
}

Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

  • Insert a character
  • Delete a character
  • Replace a character
Example

Given word1 = "mart" and word2 = "karma", return 3.

Solution: Dynamic Programming

f[i][j] = MIN(f[i-1][j-1], f[i-1][j]+1, f[i][j-1]+1) // a[i] == b[j]

= MIN(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1 // a[i] != b[j]

intialize: f[i][0] = i, f[0][j] = j

answer: f[a.length()][b.length()]

public int minDistance(String word1, String word2) {
    if (word1 == null || word2 == null) {
        return -1;
    }
    //minDistance[i][j] = minimum distance to convert first i chars of word 1
    //to first j chars of word 2
    int[][] minDistance = new int[word1.length() + 1][word2.length() + 1];
    //init the first column -- word2 is empty
    for (int i = 0; i < minDistance.length; i++) {
        minDistance[i][0] = i;
    }
    //init the first row -- word1 is empty
    for (int j = 0; j < minDistance[0].length; j++) {
        minDistance[0][j] = j;
    }

    for (int i = 1; i <= word1.length(); i++) {
        for (int j = 1; j <= word2.length(); j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                minDistance[i][j] = Math.min(Math.min(minDistance[i - 1][j - 1],
                                minDistance[i - 1][j] + 1), minDistance[i][j - 1] + 1);
            } else {
                minDistance[i][j] = Math.min(Math.min(minDistance[i - 1][j - 1],
                                minDistance[i - 1][j]), minDistance[i][j - 1]) + 1;
            }
        }
    }
    return minDistance[word1.length()][word2.length()];
}