leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0583.cpp (662B)

      1 class Solution {
      2     vector<vector<int>> dp;
      3 
      4     int solve(const string &s1, const string &s2, int i, int j) {
      5         if (i == s1.size() && j == s2.size()) return 0;
      6         if (i == s1.size() || j == s2.size()) return max(s1.size() - i, s2.size() - j);
      7         if (dp[i][j] != INT_MAX) return dp[i][j];
      8         if (s1[i] == s2[j]) return solve(s1, s2, i + 1, j + 1);
      9         return dp[i][j] = 1 + min(solve(s1, s2, i + 1, j), solve(s1, s2, i, j + 1));
     10     }
     11 
     12   public:
     13     int minDistance(const string &word1, const string &word2) {
     14         dp.resize(size(word1) + 1, vector<int>(size(word2) + 1, INT_MAX));
     15         return solve(word1, word2, 0, 0);
     16     }
     17 };