Longest Common Subsequence

题目

77. 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.

答案

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 m = A.length(), n = B.length();
        int[][] f = new int[m + 1][n + 1];
        
        for(int i = 0; i <= n; i++) {
            for(int j = 0; j <= m; j++) {
                // LCS of any string with empty string is 0
                if(i == 0 || j == 0) {
                    f[i][j] = 0;
                    continue;
                }
                
                if(A.charAt(i - 1) == B.charAt(j - 1))
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
                else
                    f[i][j] = Math.max(f[i][j - 1], f[i - 1][j]);
            }
        }
        return f[m][n];
    }
}

上面的答案f[i][j]是定义为LCS(A[0...i-1], B[0...j-1])
下面的答案f[i][j]是定义为LCS(A[0...i], B[0...j])

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 m = A.length(), n = B.length();
        if(m == 0 || n == 0) return 0;
        int[][] f = new int[m][n];
        
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(i == 0 || j == 0) {
                    if(A.charAt(i) == B.charAt(j)) f[i][j] = 1;
                    else f[i][j] = 0;
                    continue;
                }
                
                if(A.charAt(i) == B.charAt(j))
                    f[i][j] = 1 + f[i - 1][j - 1];
                else
                    f[i][j] = Math.max(f[i][j - 1], f[i - 1][j]);
            }
        }
        return f[m - 1][n - 1];
    }
}