SDE-Challenge/Day-11-longest-common-subsequence.cpp at main · looneyd-rohit/SDE-Challenge · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class Solution
{
public:
    int solve(int index1, int index2, string &s, string &t, vector<vector<int>> &dp)
    {
        // base case
        if (index1 == -1)
        {
            // string s went out of bounds
            return 0;
        }

        if (index2 == -1)
        {
            // string t went out of bounds
            return 0;
        }

        // dp check
        if (dp[index1][index2] != -1)
            return dp[index1][index2];

        // match
        if (s[index1] == t[index2])
        {
            return dp[index1][index2] = 1 + solve(index1 - 1, index2 - 1, s, t, dp);
        }
        // not match
        else
        {
            int a = solve(index1 - 1, index2, s, t, dp);
            int b = solve(index1, index2 - 1, s, t, dp);
            return dp[index1][index2] = max(a, b);
        }
    }
    int longestCommonSubsequence(string text1, string text2)
    {
        int n1 = text1.size(), n2 = text2.size();
        // memoization:
        // vector<vector<int>> dp(n1, vector<int>(n2, -1));
        // return solve(n1-1, n2-1, text1, text2, dp);

        // // tabulation:
        // vector<vector<int>> dp(n1+1, vector<int>(n2+1, 0));
        // for(int index1=1; index1<=n1; index1++){
        //     for(int index2=1; index2<=n2; index2++){
        //         // match
        //         if(text1[index1-1] == text2[index2-1]){
        //             dp[index1][index2] = 1 + dp[index1-1][index2-1];
        //         }
        //         // not match
        //         else{
        //             int a = dp[index1-1][index2];
        //             int b = dp[index1][index2-1];
        //             dp[index1][index2] = max(a, b);
        //         }
        //     }
        // }
        // return dp[n1][n2];

        // space optimization:
        vector<int> dp1(n2 + 1, 0);
        vector<int> dp2(n2 + 1, 0);
        for (int index1 = 1; index1 <= n1; index1++)
        {
            for (int index2 = 1; index2 <= n2; index2++)
            {
                // match
                if (text1[index1 - 1] == text2[index2 - 1])
                {
                    dp2[index2] = 1 + dp1[index2 - 1];
                }
                // not match
                else
                {
                    int a = dp1[index2];
                    int b = dp2[index2 - 1];
                    dp2[index2] = max(a, b);
                }
            }
            dp1 = dp2;
        }
        return dp1[n2];
    }
};