Longest Common Subsequence Solutions in C++

/// Source : https://leetcode.com/problems/longest-common-subsequence/
/// Author : liuyubobobo
/// Time   : 2019-08-22

#include <iostream>
#include <vector>

using namespace std;


/// Memory Search
/// Time Complexity: O(n * m)
/// Space Complexity: O(n * m)
class Solution {

private:
    int n, m;

public:
    int longestCommonSubsequence(string s1, string s2) {

        n = s1.size(), m = s2.size();
        vector<vector<int>> dp(n, vector<int>(m, -1));
        return dfs(s1, 0, s2, 0, dp);
    }

private:
    int dfs(const string& s1, int i, const string& s2, int j,
            vector<vector<int>>& dp){

        if(i >= n || j >= m) return 0;
        if(dp[i][j] != -1) return dp[i][j];
        int res = max(dfs(s1, i + 1, s2, j, dp), dfs(s1, i, s2, j + 1, dp));
        if(s1[i] == s2[j]) res = max(res, 1 + dfs(s1, i + 1, s2, j + 1, dp));
        return dp[i][j] = res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/longest-common-subsequence/
/// Author : liuyubobobo
/// Time   : 2019-08-22

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(n * m)
/// Space Complexity: O(n * m)
class Solution {

public:
    int longestCommonSubsequence(string s1, string s2) {

        int n = s1.size(), m = s2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++){
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
                if(s1[i] == s2[j]) dp[i + 1][j + 1] = max(dp[i + 1][j + 1], 1 + dp[i][j]);
            }
        return dp[n][m];
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/longest-common-subsequence/
/// Author : liuyubobobo
/// Time   : 2019-08-22

#include <iostream>
#include <vector>

using namespace std;


/// Dynamic Programming with Space Optimization
/// Time Complexity: O(n * m)
/// Space Complexity: O(m)
class Solution {

public:
    int longestCommonSubsequence(string s1, string s2) {

        int n = s1.size(), m = s2.size();
        vector<vector<int>> dp(2, vector<int>(m + 1, 0));
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++){
                dp[(i + 1) % 2][j + 1] = max(dp[i % 2][j + 1], dp[(i + 1) % 2][j]);
                if(s1[i] == s2[j]) dp[(i + 1) % 2][j + 1] = max(dp[(i + 1) % 2][j + 1], 1 + dp[i % 2][j]);
            }
        return dp[n % 2][m];
    }
};


int main() {

    return 0;
}