aboutsummaryrefslogtreecommitdiff
path: root/edit_distance.cpp
blob: 080df8d2b250a9aa06eab9a0147ce839cde80bc9 (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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 72. Edit Distance
#include "leetcode.h"

/*
 * given two strings 'word1' and 'word2', return minimum number of operations
 * required to convert 'word1' to 'word2'. the following operations are
 * permitted: insert character, delete character, replace character
 */

class Solution {
public:
  int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vvd(int) memo(m + 1, vector<int>(n + 1, -1));
    return editDistance(word1, word2, m, n, memo);
  }

private:
  int editDistance(string word1, string word2, int m, int n, vvd(int) memo) {
    if (m == 0)
      return memo[m][n] = n;
    if (n == 0)
      return memo[m][n] = m;
    if (memo[m][n] != -1)
      return memo[m][n];
    if (word1[m - 1] == word2[n - 1])
      return memo[m][n] = editDistance(word1, word2, m - 1, n - 1, memo);
    else {
      int insertChar = editDistance(word1, word2, m, n - 1, memo);
      int deleteChar = editDistance(word1, word2, m - 1, n, memo);
      int replacChar = editDistance(word1, word2, m - 1, n - 1, memo);
      return memo[m][n] = 1 + min({insertChar, deleteChar, replacChar});
    }
  }
};

int main() {
  Solution obj;
  cout << obj.minDistance("horse", "ros") << endl;   // expect: 3
  cout << obj.minDistance("intention", "execution"); // expect: 5
}