Length of Longest Common Subsequence (LCS) and Longest common subsequence string leetcode

Dp Learnings (27 Part Series)

1 House Robber leetcode problem
2 Jump game leetcode problem
… 23 more parts…
3 Jump game II leetcode problem
4 Cherry Pickup II Leetcode Problem
5 Partition Equals Subset Sum Leetcode problem or Subset sum equals to target
6 Maximum Sum Problem GeeksForGeeks
7 Count Palindrome Sub-Strings of a String GeeksForGeeks
8 Length of Longest Common Subsequence (LCS) and Longest common subsequence string leetcode
9 0/1 Knapsack Problem GeeksForGeeks both bounded and Unbounded
10 Shortest distance from source to all other nodes in a Directed Acyclic Graph
11 Coin change Leetcode
12 Coin Change 2 Leetcode
13 Target Sum or Partition with given difference Leetcode
14 Rod cutting Problem (similar to unbounded knapsack)
15 Length of longest common substring
16 Longest Palindromic subsequence (Same as Lcs)
17 Minimum Insertion steps needed to make a string palindrome (Same as LCS)
18 Minimum number of Insertion and deletion needed to convert String A to String B or make both the strings equal (same as lcs)
19 Shortest Common Super-sequence Leetcode (Same as Lcs string)
20 Distinct Subsequence Leetcode
21 Partition with given difference
22 Two best non overlapping events
23 Longest increasing subsequence
24 Edit distance
25 Maximum product subarray
26 Target sum
27 Maximum Multiplication Score

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.

Enter fullscreen mode Exit fullscreen mode

Solution:
Bottom up Approach(Memoization) :
Time complexity : O(m*n) where is m and n is the length of two strings a and b
space complexity : o(m*n) for using 2d dp and O(m+n) for auxiliary stack space because in worst case we will make m+n recursive calls.

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
         // we will start with the last index if its a match then we will decrement both the index
        //else we will decrement text1 index keeping text2 index same and in second method call we will decrement text2 index keeping the text1 index same 
        // by this we will cover all the possibility
        // and we will be able to get substring with the largest length common in both the Strings
        // lets optimize with dp
        int dp[][] = new int[text1.length()][text2.length()];
        for(int row[]: dp) Arrays.fill(row,-1);
        return findLcsLength(text1,text2,text1.length()-1,text2.length()-1,dp);
    }
    public int findLcsLength(String a, String b, int i,int j,int dp[][]){
        if(i<0 || j<0) return 0;
        if(dp[i][j]!=-1) return dp[i][j];
        if(a.charAt(i) ==b.charAt(j)){
            return dp[i][j] =  1 + findLcsLength(a,b,i-1,j-1,dp);
        }
        else {
            return dp[i][j]= 0+Integer.max(findLcsLength(a,b,i-1,j,dp),findLcsLength(a,b,i,j-1,dp));
        }

    }
}

Enter fullscreen mode Exit fullscreen mode

Tabulation

class Solution {
    public int longestCommonSubsequence(String str1, String str2) {
     int dp[][] = new int[str1.length()+1][str2.length()+1];
     for(int i=0;i<=str1.length();i++){
                dp[i][0] =0;
            }
            for( int i =0;i<=str2.length();i++){
                dp[0][i] = 0;
            }

            for( int i =1;i<=str1.length();i++){
                for(int j =1;j<=str2.length();j++){
                    if(str1.charAt(i-1)==str2.charAt(j-1)){
                        dp[i][j] = 1 + dp[i-1][j-1];
                    }
                    else dp[i][j] = Integer.max(dp[i][j-1],dp[i-1][j]);
                }
            }
    return dp[str1.length()][str2.length()];
    }
}

Enter fullscreen mode Exit fullscreen mode

If we have to print the longest common subsequence string, just add the following in the above code.

int p = str1.length(), q = str2.length();
        while(p>0 && q>0){
            if(str1.charAt(p-1) == str2.charAt(q-1)){
                str = str1.charAt(p-1)+ str;
                p--;
                q--;

            }
            else if(dp[p][q-1] > dp[p-1][q]){
                q--;
            }
            else p--;
        }
        System.out.println(str);

Enter fullscreen mode Exit fullscreen mode

Dp Learnings (27 Part Series)

原文链接：Length of Longest Common Subsequence (LCS) and Longest common subsequence string leetcode

文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END