1143. Longest Common Subsequence

• Visit Leetcode problem

Problem

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:
Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

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

Approach

Implementation

1. Recursion + memorization

class Solution {
    private String s1;
    private String s2;
    private Map<String, Integer> memo;

    public int longestCommonSubsequence(String text1, String text2) {
        this.s1 = text1; this.s2 = text2;
        this.memo = new HashMap<>();

        return dfs(0, 0);    
    }

    private int dfs(int i1, int i2) {
        if (i1 == s1.length() || i2 == s2.length()) {
            return 0;
        }

        String key = i1 + "_" + i2;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        int lcs = 0;
        if (s1.charAt(i1) == s2.charAt(i2)) {
            lcs = 1 + dfs(i1+1, i2+1);
        } else {
            lcs = Math.max(dfs(i1+1, i2), dfs(i1, i2+1));
        }
        
        memo.put(key, lcs);
        return lcs;
    }
}

Dynamic programming

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length(); int m = text2.length();
        int[][] dp = new int[n+1][m+1];

        for (int c = 0; c <= m; c++) dp[n][c] = 0;
        for (int r = 0; r <= n; r++) dp[r][m] = 0;

        for (int r = n-1; r >= 0; r--) {
            for (int c = m-1; c >= 0; c--) {
                if (text1.charAt(r) == text2.charAt(c)) {
                    dp[r][c] = 1 + dp[r+1][c+1];
                } else {
                    dp[r][c] = Math.max(dp[r+1][c], dp[r][c+1]);
                }
            }
        }

        return dp[0][0];
    }
}