1143. Longest Common Subsequence (Medium)

https://leetcode.com/problems/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:

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

Solutions

1.

class Solution {

    // This problem reminds me another problem longest consecutive common subsequence. The idea is similar that both
    // employ dynamic programming. Here, I will implement the solution for longest consecutive common subsequence.

    private int longestConsecutiveCommonSubsequence(String text1, String text2) {
        int ans = 0;

        if (text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0) {
            return ans;
        }

        int len1 = text1.length();
        int len2 = text2.length();

        // subject to text1.length() < text2.length()

        // row represents the length of text2, col represents the length of text1
        // initially, values for every cell is 0 by default.
        int[][] dp = new int[len2 + 1][len1 + 1];

        for (int i = 1; i <= len2; i++) {
            for (int j = 1; j <= len1; j++) {
                if (text1.charAt(j - 1) == text2.charAt(i - 1)) {
                    // text1 and text2 both move forward one step
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = 0;
                }

                ans = Math.max(ans, dp[i][j]);
            }
        }

        return ans;
    }

    public int longestCommonSubsequence(String text1, String text2) {
        if (text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0) {
            return 0;
        }

        int len1 = text1.length();
        int len2 = text2.length();

        // row represents the length of text1, col represents the length of text2
        // initially, values for every cell is 0 by default.
        int[][] dp = new int[len1 + 1][len2 + 1];

        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    // text1 and text2 both move forward one step
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[len1][len2];
    }

    private int max(int x, int y, int z) {
        int tmp = Math.max(x, y);

        return Math.max(tmp, z);
    }
}

2.

class Solution2 {

    // Inspired by https://leetcode.com/problems/longest-common-subsequence/discuss/349150/Simple-DP-in-Python-O(mn)-time-O(n)-memory-explained

    // This solution saved more memory space. But a little different from the original one because we did not strictly
    // make the text1 and text2 subject to text1.length > text2.length.

    public int longestCommonSubsequence(String text1, String text2) {
        if (text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0) {
            return 0;
        }

        int len1 = text1.length();
        int len2 = text2.length();

        // dp[curP][j] only consider the results of dp[curP-1][j], dp[curP-1][j-1] and dp[curP][j-1].
        // results of dp[curP-2][*] will never be used later.
        // So we can simplify the curP as current, curP-1 as previous, thus we only have to allocate
        // int[2][len1+1] space and that will be enough.

        int[][] dp = new int[2][len2 + 1];

        for (int i = 1; i <= len1; i++) {

            // parity
            int prevP = (i - 1) % 2;
            int curP = i % 2;

            dp[curP][0] = 0;

            for (int j = 1; j <= len2; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    // text1 and text2 both move forward one step
                    dp[curP][j] = dp[prevP][j - 1] + 1;
                } else {
                    dp[curP][j] = max(dp[prevP][j - 1], dp[prevP][j], dp[curP][j - 1]);
                }
            }
        }

        return dp[len1 % 2][len2];
    }

    private int max(int x, int y, int z) {
        int tmp = Math.max(x, y);

        return Math.max(tmp, z);
    }
}

Incorrect Solutions

References

  1. https://leetcode.com/problems/longest-common-subsequence/discuss/349150/Simple-DP-in-Python-O(mn)-time-O(n)-memory-explained
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""