Problem Statement:
You are given 2 strings you need to return the longest common subsequence between two strings.
Example
str1 = ABC str2 = AC Output: 2 The LCS of the 2 strings is "AC" hence 2.
Solution
The solution is similar to LCS, but here we have 2 different strings.
So here we have to use bottom-up DP, that will track LCS.
if a[i] == b[j], LCS for i and j would be 1.
else we take the largest LCS max(m[i – 1][j], m[i][j – 1]).
Time complexity: O(nm)
The filled DP array will look like:
1 1 1
1 1 1
1 2 2
1 2 2
1 2 2
1 2 3
Solution in C++
#include <vector> #include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <string> #include <unordered_map> #include <vector> #include <sstream> using namespace std; int longest_common_subsequence(string &a, string &b) { vector<vector<short>> m(a.size() + 1, vector<short>(b.size() + 1)); for (auto i = 1; i <= a.size(); ++i) { for (auto j = 1; j <= b.size(); ++j) { if (a[i - 1] == b[j - 1]) m[i][j] = m[i - 1][j - 1] + 1; else m[i][j] = max(m[i - 1][j], m[i][j - 1]); } } return m[a.size()][b.size()]; } int main() { string a = "abccde"; string b = "ace"; cout<<"THe LCS of 2 strings is = "<<longest_common_subsequence(a, b)<<endl; return 0; }
Output:
THe LCS of 2 strings is = 3