aboutsummaryrefslogtreecommitdiff
path: root/delete_operation_2string.cpp
blob: b6e38e4414fc8519b4fb87ddc92dd932b3b32b17 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include "leetcode.h"

class Solution {
public:
  int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    if (m < n) {
      swap(word1, word2);
      swap(n, m);
    }
    vector<int> last(n + 1, 0), curr(n + 1, 0);
    for (char char1 : word1) {
      for (int i = 0; i < n; i++)
        curr[i + 1] =
            char1 == word2[i] ? last[i] + 1 : max(curr[i], last[i + 1]);
      swap(last, curr);
    }
    return m + n - 2 * last[n];
  }
};

int main() {
  Solution obj;
  string word1 = "sea", word2 = "eat";
  cout << obj.minDistance(word1, word2);
}