leetcode-solution/code/72.edit-distance.cpp at master · Testzero-wz/leetcode-solution · GitHub

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
42
43
44
45
46
47
48
49
50
/*
 * @lc app=leetcode id=72 lang=cpp
 *
 * [72] Edit Distance
 */
#include <string>
using namespace std;
// @lc code=start
class Solution
{
public:
    int l[501];
    int h[501];
    int minDistance(string word1, string word2)
    {
        int l1 = word1.length();
        int l2 = word2.length();
        if (l1 == 0 || l2 == 0)
            return max(l1, l2);
        int *low = l;
        int *high = h;
        bool exchange = false;
        // init
        for (int j = 0; j <= l2; j++)
            low[j] = j;
        // dp
        for (int i = 1; i <= l1; i++)
        {
            for (int j = 1; j <= l2; j++)
            {
                high[0] = i;
                if (word1[i - 1] == word2[j - 1])
                {
                    high[j] = low[j - 1];
                }
                else
                {
                    int tmp = min(high[j - 1], low[j - 1]);
                    high[j] = min(tmp, low[j]) + 1;
                }
            }
            exchange = true;
            int *tmp_ptr = low;
            low = high;
            high = tmp_ptr;
        }
        return low[l2];
    }
};
// @lc code=end