leetcode

Solution to some Leetcode problems written in C++

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

0712.cpp (846B)

0 class Solution { 1 int dp[1001][1001]; 2 int rec(const string &s1, const string &s2, int l1, int l2) { 3 if (l1 >= s1.size() && l2 >= s2.size()) return 0; 4 if (dp[l1][l2] != -1) return dp[l1][l2]; 5 6 int res = INT_MAX; 7 if (s1[l1] == s2[l2]) res = min(res, rec(s1, s2, l1 + 1, l2 + 1)); 8 res = min(res, s1[l1] + rec(s1, s2, l1 + 1, l2)); 9 res = min(res, s2[l2] + rec(s1, s2, l1, l2 + 1)); 10 11 return dp[l1][l2] = res; 12 } 13 14 public: 15 Solution() { memset(dp, 0xFF, sizeof(dp)); } 16 int minimumDeleteSum(const string &s1, const string &s2) { 17 for (int i = s1.size() - 1, sum = 0; i >= 0; i--) 18 dp[i][s2.size()] = sum += s1[i]; 19 for (int i = s2.size() - 1, sum = 0; i >= 0; i--) 20 dp[s1.size()][i] = sum += s2[i]; 21 22 return rec(s1, s2, 0, 0); 23 } 24 };