LCS of 3 strings
Posted: 6 Nov, 2020
Given three strings A, B and C, the task is to find the length of the longest common sub-sequence in all the three strings A, B and C.
A subsequence of a string is a new string generated from the original string with some characters(can be 0) deleted without changing the relative order of the remaining characters. (For eg, "cde" is a subsequence of "code" while "cdo" is not). A common subsequence of two or more strings is a subsequence that is common to all the strings.
You don’t have to print anything, it has already been taken care of. Just complete the function. If there is no common subsequence, return 0.
The first line of input contains an integer ‘T’ denoting the number of test cases. The first line of the testcase contains three space-separated positive integers n, m, k denoting the length of the strings A, B, C respectively. The second line of the testcase contains the string A. The third line of the testcase contains the string B. The fourth line of the testcase contains the string C.
For each test case, return the length of the longest common subsequence in all the three strings A, B, and C.
1 <= T <= 5 1 <= n, m, k <= 100 Where ‘T’ is the total number of test cases and n, m, k are the length of strings A, B, and C respectively. Time limit: 1 second
This problem can be solved by solving its subproblems and then combining the solutions of the solved subproblems to solve the original problem. We will do this using recursion.
- The idea is to use recursion to reduce the big problem into several small subproblems.
- We will call a recursive function ‘helper’ that takes all the three strings and their lengths as arguments and returns us the length of the longest common sub-sequence of these strings and store it in a variable say ‘answer’.
- The algorithm for the helper function will be as follows:
Int helper(A, B, C, n, m, k):
A. If n or m or k becomes 0, return 0.
B. Now compare A[n-1], B[m-1] and C[k-1],
- If they are equal, return 1 + helper(A, B, C, n-1, m-1, k-1).
- If they are not equal, return max(helper(A, B, C, n-1, m, k), helper(A, B, C, n, m-1, k), helper(A, B, C, n, m, k-1).)
- Return the ‘answer’.
Palindromes And Indexes
Posted: 7 Jul, 2021
Ninja's Frustrating Homework
Posted: 8 Jul, 2021
Longest Common Prefix
Posted: 24 Jul, 2021
Posted: 29 Jul, 2021
Posted: 21 Aug, 2021