leetcode

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

0072.cpp (1373B)

      1 class Solution {
      2   public:
      3     int minDistance(string word1, string word2) {
      4         int n = word1.size(), m = word2.size();
      5         vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
      6         for (int i = 1; i <= n; i++)
      7             dp[i][0] = i;
      8         for (int j = 1; j <= m; j++)
      9             dp[0][j] = j;
     10 
     11         for (int i = 1; i <= n; i++) {
     12             for (int j = 1; j <= m; j++) {
     13                 if (word1[i - 1] == word2[j - 1])
     14                     dp[i][j] = dp[i - 1][j - 1];
     15                 else
     16                     dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;
     17             }
     18         }
     19         return dp.back().back();
     20     }
     21 };
     22 
     23 // Improvement, use two DP arrays instead of a matrix
     24 class Solution {
     25   public:
     26     int minDistance(const string &word1, const string &word2) {
     27         int n = word1.size(), m = word2.size();
     28         if (n == 0 || m == 0) return max(m, n);
     29         vector<int> dp1(m + 1, 0), dp2(m + 1, 0);
     30         iota(dp1.begin(), dp1.end(), 0);
     31         for (int i = 1; i <= n; i++) {
     32             dp2[0]++;
     33             for (int j = 1; j <= m; j++) {
     34                 if (word1[i - 1] == word2[j - 1])
     35                     dp2[j] = dp1[j - 1];
     36                 else
     37                     dp2[j] = min({dp1[j - 1], dp2[j - 1], dp1[j]}) + 1;
     38             }
     39             dp1 = dp2;
     40         }
     41         return dp2[m];
     42     }
     43 };