1143. Longest Common Subsequence

Description

The problem is to find the length of the longest common subsequence (LCS) between two strings, text1 and text2. A subsequence is a sequence that appears in the same relative order but not necessarily contiguously. For example, "ace" is a subsequence of "abcde".

Intuition

The intuition behind solving this problem is to use dynamic programming (DP) to avoid redundant calculations and efficiently find the LCS. By breaking the problem into smaller subproblems and storing the results of these subproblems, we can build up the solution to the original problem.

Approach

1. Define the DP Array: - Create a 2D DP array, where dp[i][j] represents the length of the LCS of text1[0:i] and text2[0:j].
2. Base Cases: - If either string is empty, the LCS length is 0. Initialize dp[0][j] and dp[i][0] to 0 for all i and j.
3. State Transition: - If the characters text1[i-1] and text2[j-1] are the same, then dp[i][j] = dp[i-1][j-1] + 1. - If the characters are different, then dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
4. Result: - The length of the LCS of text1 and text2 will be dp[len(text1)][len(text2)].

Complexity

Time Complexity:

O(m * n), where m is the length of text1 and n is the length of text2. This is because we are filling out a 2D DP array of size m * n.

Space Complexity:

O(m * n) for the DP array. However, this can be optimized to O(min(m, n)) by using a rolling array technique.

Code

C++

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        unordered_map memoMap;
        return lcs(text1, text2, 0, 0, memoMap);
    }

private:
    int lcs(const string& text1, const string& text2, int i, int j, unordered_map& memoMap) {
        if (i == text1.length() || j == text2.length()) return 0;
        string key = to_string(i) + "," + to_string(j);
        if (memoMap.find(key) != memoMap.end()) return memoMap[key];
        
        int result;
        if (text1[i] == text2[j]) {
            result = 1 + lcs(text1, text2, i + 1, j + 1, memoMap);
        } else {
            result = max(lcs(text1, text2, i, j + 1, memoMap), lcs(text1, text2, i + 1, j, memoMap));
        }
        memoMap[key] = result;
        return result;
    }
};

Python

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memoMap = {}
        
        def lcs(i, j):
            if i == len(text1) or j == len(text2):
                return 0
            key = (i, j)
            if key in memoMap:
                return memoMap[key]
            if text1[i] == text2[j]:
                result = 1 + lcs(i + 1, j + 1)
            else:
                result = max(lcs(i, j + 1), lcs(i + 1, j))
            memoMap[key] = result
            return result
        
        return lcs(0, 0)

Java

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        Map memoMap = new HashMap<>();
        return lcs(text1, text2, 0, 0, memoMap);
    }

    private int lcs(String text1, String text2, int i, int j, Map memoMap) {
        if (i == text1.length() || j == text2.length()) return 0;
        String key = i + "," + j;
        if (memoMap.containsKey(key)) return memoMap.get(key);

        int result;
        if (text1.charAt(i) == text2.charAt(j)) {
            result = 1 + lcs(text1, text2, i + 1, j + 1, memoMap);
        } else {
            result = Math.max(lcs(text1, text2, i, j + 1, memoMap), lcs(text1, text2, i + 1, j, memoMap));
        }
        memoMap.put(key, result);
        return result;
    }
}

JavaScript

var longestCommonSubsequence = function(text1, text2) {
    let memoMap = new Map();
    const lcs = (i, j) => {
        if (i === text1.length || j === text2.length) return 0;
        let key = `${i},${j}`;
        if (memoMap.has(key)) return memoMap.get(key);
        let result;
        if (text1[i] === text2[j]) {
            result = 1 + lcs(i + 1, j + 1);
        } else {
            result = Math.max(lcs(i, j + 1), lcs(i + 1, j));
        }
        memoMap.set(key, result);
        return result;
    }
    return lcs(0, 0);
};