1143. Longest Common Subsequence

Description

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.

Constraints

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

• text1 and text2 consist of only lowercase English characters.

Approach

Links

• Binarysearch

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: text1 = "abc", text2 = "abc"

Output: 3

Explanation: The longest common subsequence is "abc" and its length is 3.

Example 2

Input: text1 = "abc", text2 = "def"

Output: 0

Explanation: There is no such common subsequence, so the result is 0.

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        if(text1 == null || text2 == null || text1.isEmpty() || text2.isEmpty()) {
            return 0;
        }
        int t1Len = text1.length(), t2Len = text2.length();
        int[][] dp = new int[t1Len+1][t2Len+1];
        
        for(int i = 1; i <= t1Len; i++) {
            for(int j = 1; j <= t2Len; 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-1][j], dp[i][j-1]);
                }
            }
        }
        
        return dp[t1Len][t2Len];
    }
}

Follow up