leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1143.cpp (1310B)

0 // Top-down DP 1 class Solution { 2 int search(const string &text1, const string &text2, int si, int sj, vector<vector<int>> &dp) { 3 if (si == text1.size() || sj == text2.size()) return 0; 4 if (dp[si][sj] != -1) return dp[si][sj]; 5 int len = 0, i = si, j = sj; 6 while (i < text1.size() && j < text2.size() && text1[i] == text2[j]) 7 i++, j++, len++; 8 9 if (i == text1.size() || j == text2.size()) return dp[si][sj] = len; 10 return dp[si][sj] = len + max(search(text1, text2, i + 1, j, dp), search(text1, text2, i, j + 1, dp)); 11 } 12 13 public: 14 int longestCommonSubsequence(string text1, string text2) { 15 vector<vector<int>> dp(text1.size(), vector<int>(text2.size(), -1)); 16 return search(text1, text2, 0, 0, dp); 17 } 18 }; 19 20 // Bottom-up DP 21 class Solution { 22 public: 23 int longestCommonSubsequence(string text1, string text2) { 24 vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0)); 25 for (int i = 0; i < text1.size(); i++) 26 for (int j = 0; j < text2.size(); j++) 27 if (text1[i] == text2[j]) 28 dp[i + 1][j + 1] = 1 + dp[i][j]; 29 else 30 dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]); 31 32 return dp.back().back(); 33 } 34 };