commit d66cc2fc391d504ec4e8d77df4f887ea70d7ac34
parent 2af78f2f8c305bdff64e5babdca52972933e0cfb
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Wed, 8 Feb 2023 21:08:12 +0100
Dynamic Programming I: Day 19
Diffstat:
3 files changed, 58 insertions(+), 0 deletions(-)
diff --git a/Problems/0072.cpp b/Problems/0072.cpp
@@ -0,0 +1,19 @@
+class Solution {
+public:
+ int minDistance(string word1, string word2) {
+ int n = word1.size(), m = word2.size();
+ vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
+ for (int i = 1; i <= n; i++) dp[i][0] = i;
+ for (int j = 1; j <= m; j++) dp[0][j] = j;
+
+ for (int i = 1; i <= n; i++) {
+ for (int j = 1; j <= m; j++) {
+ if (word1[i - 1] == word2[j - 1])
+ dp[i][j] = dp[i - 1][j - 1];
+ else
+ dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;
+ }
+ }
+ return dp.back().back();
+ }
+};
diff --git a/Problems/1143.cpp b/Problems/1143.cpp
@@ -0,0 +1,37 @@
+// Top-down DP
+class Solution {
+ int search(const string &text1, const string &text2, int si, int sj,
+ vector<vector<int>> &dp) {
+ if (si == text1.size() || sj == text2.size()) return 0;
+ if (dp[si][sj] != -1) return dp[si][sj];
+ int len = 0, i = si, j = sj;
+ while (i < text1.size() && j < text2.size() && text1[i] == text2[j])
+ i++, j++, len++;
+
+ if (i == text1.size() || j == text2.size()) return dp[si][sj] = len;
+ return dp[si][sj] = len + max(search(text1, text2, i + 1, j, dp),
+ search(text1, text2, i, j + 1, dp));
+ }
+
+public:
+ int longestCommonSubsequence(string text1, string text2) {
+ vector<vector<int>> dp(text1.size(), vector<int>(text2.size(), -1));
+ return search(text1, text2, 0, 0, dp);
+ }
+};
+
+// Bottom-up DP
+class Solution {
+public:
+ int longestCommonSubsequence(string text1, string text2) {
+ vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
+ for (int i = 0; i < text1.size(); i++)
+ for (int j = 0; j < text2.size(); j++)
+ if (text1[i] == text2[j])
+ dp[i + 1][j + 1] = 1 + dp[i][j];
+ else
+ dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
+
+ return dp.back().back();
+ }
+};
diff --git a/README.md b/README.md
@@ -66,6 +66,7 @@ for solving problems.
| 0066 | Easy | [Plus One](Problems/0066.cpp) |
| 0067 | Easy | [Add Binary](Problems/0067.cpp) |
| 0070 | Easy | [Climbing Stairs](Problems/0070.cpp) |
+| 0072 | Hard | [Edit Distance](Problems/0072.cpp) |
| 0074 | Medium | [Search a 2D Matrix](Problems/0074.cpp) |
| 0075 | Medium | [Sort Colors](Problems/0075.cpp) |
| 0077 | Medium | [Combinations](Problems/0077.cpp) |
@@ -322,6 +323,7 @@ for solving problems.
| 1099 | Easy | [Replace Elements with Greatest Element on Right Side](Problems/1099.cpp) |
| 1129 | Medium | [Shortest Path with Alternating Colors](Problems/1129.cpp) |
| 1137 | Easy | [N-th Tribonacci Number](Problems/1137.cpp) |
+| 1143 | Medium | [Longest Common Subsequence](Problems/1143.cpp) |
| 1202 | Medium | [Smallest String With Swaps](Problems/1202.cpp) |
| 1209 | Medium | [Remove All Adjacent Duplicates in String II](Problems/1209.cpp) |
| 1290 | Easy | [Convert Binary Number in a Linked List to Integer](Problems/1290.cpp) |
