leetcode

0 class Solution {

1 public:

2 int minDistance(string word1, string word2) {

3 int n = word1.size(), m = word2.size();

4 vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

5 for (int i = 1; i <= n; i++)

6 dp[i][0] = i;

7 for (int j = 1; j <= m; j++)

8 dp[0][j] = j;

9

10 for (int i = 1; i <= n; i++) {

11 for (int j = 1; j <= m; j++) {

12 if (word1[i - 1] == word2[j - 1])

13 dp[i][j] = dp[i - 1][j - 1];

14 else

15 dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;

16 }

17 }

18 return dp.back().back();

19 }

20 };

21

22 // Improvement, use two DP arrays instead of a matrix

23 class Solution {

24 public:

25 int minDistance(const string &word1, const string &word2) {

26 int n = word1.size(), m = word2.size();

27 if (n == 0 || m == 0) return max(m, n);

28 vector<int> dp1(m + 1, 0), dp2(m + 1, 0);

29 iota(dp1.begin(), dp1.end(), 0);

30 for (int i = 1; i <= n; i++) {

31 dp2[0]++;

32 for (int j = 1; j <= m; j++) {

33 if (word1[i - 1] == word2[j - 1])

34 dp2[j] = dp1[j - 1];

35 else

36 dp2[j] = min({dp1[j - 1], dp2[j - 1], dp1[j]}) + 1;

37 }

38 dp1 = dp2;

39 }

40 return dp2[m];

41 }

42 };