Search
Question:
How to do LCS of three strings using C++

Summary

Suppose we are taking two functions ‘lcs’ and ‘LCSof3’. These two functions will help us to find the Longest Common Sequences (LCS) between two strings (‘A’, ‘B’) and three strings (‘A’, ‘B’, and ‘C’).


Solution

class Solution

{

    public:

        int lcs(string A, string B, int n1, int n2){

            int dp[n1+1][n2+1];

            for(int i=0;i<=n1;i++){

                for(int j=0;j<=n2;j++){

                    if(i == 0 || j == 0){

                        dp[i][j] = 0;

                        continue;

                    }

                    if(A[i-1] == B[j-1])

                        dp[i][j] = 1 + dp[i-1][j-1];

                    else

                        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

                }

            }

            return dp[n1][n2];

        }

        int LCSof3 (string A, string B, string C, int n1, int n2, int n3)

        {

            int dp[n1+1][n2+1][n3+1];

            int res = -1;

            for(int i=0;i<=n1;i++){

                for(int j=0;j<=n2;j++){

                    for(int k=0;k<=n3;k++){

                        if(i == 0 || j == 0 || k == 0){

                            dp[i][j][k] = 0;

                            continue;

                        }

                        if(A[i-1] == B[j-1] && B[j-1] == C[k-1])

                            dp[i][j][k] = 1 + dp[i-1][j-1][k-1];

                        else

                            dp[i][j][k] = max(max(dp[i-1][j][k], dp[i][j-1][k]),dp[i][j][k-1]);

                        // if(dp[i][j][k] > res)

                        //     res = dp[i][j][k];

                    }

                }

            }

            return dp[n1][n2][n3];   

        }

};


Explanation

lcs function:


  • Two strings (A and B) and their corresponding lengths (n1 and n2) are supplied to the lcs function.

  • It stores the length of the LCS for each potential subproblem using a 2D array called dp.

  • The two strings' lengths are iterated through in the nested loops, and the dp array is filled using the following logic:

  • The LCS length is set to 0 if any of the strings is zero in length.


LCSof3 function:

  • The LCSof3 function takes three strings (A, B, and C) and their respective lengths (n1, n2, and n3).

  • It uses a 3D array dp to store the length of the LCS for all possible subproblems involving the three strings.



Answered by:> >jaswanthvuda

Credit:> >GeekforGeeks


Suggested blogs:

>How to find the minimum number of jumps to reach the end of the array using C++

>How to check whether string (of brackets) is balanced or not using C++

>How to distribute candies in a binary tree using C++

>How to remove the loop from the linked list using C++

>How to find the Kth smallest number given in the array using C++

>How to Detect cycle in a directed graph?


Submit
0 Answers
Top Questions
15-02-2024

Calculating the Diameter of a Binary Tree with C++

02-03-2024

How to measure the peak of an element using C++

29-01-2024

How to distribute candies in a binary tree using C++

04-03-2024

How to find the largest number formed from an array using C++

01-02-2024

How to Find triplets with zero sum?

Related Questions

Use Binary Search and find index of a target element in array using C++
img
How to measure the peak of an element using C++
img
How to find the largest number formed from an array using C++
img
How to check whether string (of brackets) is balanced or not using C++
img
How to move all zeroes in an array to the end? C++
img