Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence.

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. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

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
2
3
    1 <= text1.length <= 1000
    1 <= text2.length <= 1000
    The input strings consist of lowercase English characters only.

Solution:

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
class Solution {
    
    private Map<Integer, Integer> map = new HashMap<>();
    private String _text1, _text2;
    
    private Integer buildKey(int len1, int len2) {
        return Objects.hash(len1 + "_" + len2);
    }
    
    public int myLCS(int len1, int len2) {
        if (len1 == 0 || len2 == 0) {
            return 0;
        }
        
        Integer key = buildKey(len1, len2);
        
        if (map.containsKey(key)) {
            return map.get(key);
        }
        
        if (_text1.charAt(len1 - 1) == _text2.charAt(len2 - 1)) {
            int value = 1 + myLCS(len1 - 1, len2 - 1);
            map.put(key, value);
            return value;
        }
        
        int left = myLCS(len1, len2 - 1);
        int right = myLCS(len1 - 1, len2);
      
        map.put(key, Math.max(left, right));
        
        return Math.max(left, right);
    }
    
    public int iterativeLCS(String a, String b) {
        int n = a.length();
        int m = b.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (a.charAt(i) == b.charAt(j)) {
                    dp[i+1][j+1] = 1 + dp[i][j];
                } else {
                    dp[i+1][j+1] = Math.max(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        }
        return dp[n][m];
    }
    
    public int longestCommonSubsequence(String _text1, String _text2) {
        return iterativeLCS(_text1, _text2);
    }
    
    private Integer buildKey(String text1, String text2) {
        return Objects.hashCode(text1 + "_" + text2);
    }
    
    public int longestCommonSubsequence2(String text1, String text2) {
        
        if (text1.isEmpty() || text2.isEmpty()) {
            return 0;
        }
        
        Integer key = buildKey(text1, text2);
        
        if (map.containsKey(key)) {
            return map.get(key);
        }
        
        if (text1.charAt(text1.length() - 1) == text2.charAt(text2.length() - 1)) {
            text1 = text1.substring(0, text1.length() - 1);
            text2 = text2.substring(0, text2.length() - 1);
            int value = 1 + longestCommonSubsequence(text1, text2);
            
            map.put(key, value);
            return value;
        }
        
        int left = longestCommonSubsequence(text1, text2.substring(0, text2.length() - 1));
        int right = longestCommonSubsequence(text1.substring(0, text1.length() - 1), text2);
      
        map.put(key, Math.max(left, right));
        
        return Math.max(left, right);
    }
    
    public int longestCommonSubsequence1(String text1, String text2) {
        
        if (text1.isEmpty() || text2.isEmpty()) {
            return 0;
        }
        
        if (text1.charAt(text1.length() - 1) == text2.charAt(text2.length() - 1)) {
            text1 = text1.substring(0, text1.length() - 1);
            text2 = text2.substring(0, text2.length() - 1);
            return 1 + longestCommonSubsequence(text1, text2);
        }
        
        return Math.max(
            longestCommonSubsequence(text1, text2.substring(0, text2.length() - 1)),
            longestCommonSubsequence(text1.substring(0, text1.length() - 1), text2)
        );
    }
}