Leetcode 1143： Longest Common Subsequence

Description

Difficulty: Medium

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".

A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:
1
2
3
Input: text1 = "abcde", text2 = "ace" 
   Output: 3  
   Explanation: The longest common subsequence is "ace" and its length is 3.
Example 2:
1
2
3
Input: text1 = "abc", text2 = "abc"
>Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.
Example 3:
1
2
3
   Input: text1 = "abc", text2 = "def"
   Output: 0
Explanation: There is no such common subsequence, so the result is 0.
Constraints:

1 <= text1.length, text2.length <= 1000

text1 and text2 consist of only lowercase English characters.

Solution - 1： Dynamic Programming

We can compare the last two characters c1, c2 (if exist) of the string s1, s2

if they’re equal, LSE(s1, s2) = LSE(s1 without c1, s2 without c2) + 1
if not equal, LSE(s1, s2) = max{ LSE(s1 without c1, s2), LSE(s1, s2 without c2)}

Recursion

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        return dp(text1, text2);
    }
    
    private int dp(String text1, String text2) {
        if (text1 == "" || text2 == "") {
            return 0;
        }
        
        int length1 = text1.length();
        int length2 = text2.length();
            
        // get the last character of both strings
        char lastChar1 = text1.charAt(length1-1);
        char lastChar2 = text2.charAt(length2-1);
        
        // recurrence relation
        if (lastChar1 == lastChar2) {
            return 1 + longestCommonSubsequence(text1.substring(0, length1-1), text2.substring(0, length2-1));
        } else {
            return Math.max(
                longestCommonSubsequence(text1.substring(0, length1-1), text2),
                longestCommonSubsequence(text1, text2.substring(0, length2-1)));
        }
    }
}

Time Limit Exceeded at about half of the test cases since some subproblems are calculated multiple times, we should apply dynamic programming using memorization

Running time: O(2^(n))

DP Top-Down

class Solution {
    
    private HashMap<HashMap<String, String>, Integer> memo = new HashMap<HashMap<String, String>, Integer>();
    
    public int longestCommonSubsequence(String text1, String text2) {
        return dp(text1, text2);
    }
    
    private int dp(String text1, String text2) {
        if (text1 == "" || text2 == "") {
            return 0;
        }
        
        HashMap<String, String> key = new HashMap<String, String>();
        key.put(text1, text2);
        
        // if it's already calculated, return the value directly
        if(memo.containsKey(key)) {
            return memo.get(key);
        }
        
        int length1 = text1.length();
        int length2 = text2.length();
            
        // get the last character of both strings
        char lastChar1 = text1.charAt(length1-1);
        char lastChar2 = text2.charAt(length2-1);
        
        // recurrence relation
        if (lastChar1 == lastChar2) {
            memo.put(key, 1 + dp(text1.substring(0, length1-1), text2.substring(0, length2-1)));
        } else {
            memo.put(key, Math.max(
                dp(text1.substring(0, length1-1), text2),
                dp(text1, text2.substring(0, length2-1))));
        }
        
        return memo.get(key);
    }
}

Time Limit Exceeded at 42/44

Running time: O(m*n)

DP Bottom-up

We can use the iterative way to accelerate the running time

class Solution {
    
    public int longestCommonSubsequence(String text1, String text2) {
        int length1 = text1.length();
        int length2 = text2.length();
        
        int[][] dp = new int[length1 + 1][length2 + 1];
        
        for (int i=0; i<=length1; i++) { // O(n)
            dp[i][0] = 0;
        }
        for (int j=0; j<=length2; j++) { // O(m)
            dp[0][j] = 0;
        }
        
        // fill the 2d array dp row by row and from left to right
        for (int i=1; i<=length1; i++) { // O(n*m)
            for (int j=1; j<=length2; j++) {
                if (text1.charAt(i-1) == text2.charAt(j-1)) {
                    dp[i][j] = 1 + dp[i-1][j-1];
                } else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
                
            }
        }
        return dp[length1][length2];
    }
}

Accepted

Running time: O(n*m)

Summary

Surprisingly the iterative approach is quicker than the recursive approach, from the logic it’s also easier to implement
top-down is implemented with a recursive function and hash map,
whereas bottom-up is implemented with nested for loops and an array.

总之希望自己能坚持下去，每周记录分享几道有趣的题和解法。也欢迎大家留言讨论补充(●’◡’●)