Lintcode. Longest Common Subsequence

Given two strings, find the longest common subsequence (LCS).
Your code should return the length of LCS.

Clarification
What’s the definition of Longest Common Subsequence?

https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Example
For “ABCD” and “EDCA”, the LCS is “A” (or “D”, “C”), return 1.
For “ABCD” and “EACB”, the LCS is “AC”, return 2.

 

Java (bottom-up)
Time complexity: O(N*M), N – len of string1, M – len of string2
Space complexity: O(N*M), N – len of string1, M – len of string2

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 || A.length() == 0 || B.length() == 0){
            return 0;
        }
        
        int[][] dp = 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){
                    dp[i][j] = A.charAt(i) == B.charAt(j) ? 1 : 0;
                } else {
                    int same = A.charAt(i) == B.charAt(j) ? 1 : 0;
                    if (same == 1){
                        dp[i][j] = same + ((i > 0 && j > 0) ? dp[i-1][j-1] : 0);
                    } else{
                        int prevNonSymm1 = j > 0 ? dp[i][j-1] : Integer.MIN_VALUE; 
                        int prevNonSymm2 = i > 0 ? dp[i-1][j] : Integer.MIN_VALUE;
                        dp[i][j] = Math.max(prevNonSymm1, prevNonSymm2);   
                    }
                }
            }    
        }
        return dp[A.length()-1][B.length() - 1];
    }
}

 

Python (bottom-up)

class Solution:
    """
    @param A, B: Two strings.
    @return: The length of longest common subsequence of A and B.
    """
    def longestCommonSubsequence(self, A, B):
        # write your code here
        if (not len(A) or not len(B)):
            return 0
            
        dp = [[0 for x in range(len(A))] for y in range(len(B))] 
        
        for x in range(len(A)):
            for y in range(len(B)):
                if A[x] == B[y]:
                    dp[x][y] = 1 if not x or not y else 1 + dp[x-1][y-1]
                elif (x > 0 and y > 0):
                    dp[x][y] = max(dp[x-1][y], dp[x][y-1])
                else: 
                    dp[x][y] = dp[x-1][y] if x else dp[x][y-1] if y else 0

        return dp[len(A)-1][len(B)-1]

Java (topdown)
Time complexity: O(N*M), N – len of string1, M – len of string2
Space complexity: O(N*M) (dp array) + O(N*M) (recursive stack), N – len of string1, M – len of string2

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 || A.length() == 0 || B.length() == 0){
            return 0;
        }
        
        int[][] dp = new int[A.length()][B.length()];
        
        return lcs(A, B, 0, 0, dp);
    }
    
    private int lcs(String A, String B, int idxa, int idxb, int[][] dp){
        if (idxa == A.length() || idxb == B.length()){
            return 0;
        }
        
        if (dp[idxa][idxb] != 0){
            return dp[idxa][idxb];
        }
        
        int lcsLen = 0;
        
        if (A.charAt(idxa) == B.charAt(idxb)){
            lcsLen = 1 + lcs(A, B, idxa+1, idxb+1, dp);    
        } else {
            lcsLen = Math.max(lcs(A, B, idxa+1, idxb, dp), lcs(A, B, idxa, idxb+1, dp)); 
        }
        
        dp[idxa][idxb] = lcsLen;
        
        return lcsLen;
    }
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s