LeetCode 72 Edit Distance

概述

https://leetcode.com/problems/edit-distance/

最值问题，显然动态规划

动态规划法

1. base case：一个为空时，距离为另一个的长度
2. 状态：两个字符串的处理索引
3. 选择：删，改，增
4. dp 函数 / 数组的定义：dp[word1 idx][word2 idx] = 最小编辑次数

一次 AC 了，这就是 hard 吗？感动感动。

代码：

class Solution {
public:
    vector<vector<int>> dp;
    string word1;
    string word2;
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size(), vector<int>(word2.size(), -1));
        this->dp = dp;
        this->word1 = word1;
        this->word2 = word2;
        return helper(0, 0);
    }
    
    int helper(int i, int j) {
        if (i == word1.size()) return word2.size() - j;
        if (j == word2.size()) return word1.size() - i;
        if (dp[i][j] != -1) return dp[i][j];
        if (word1[i] == word2[j]) {
            dp[i][j] = helper(i+1, j+1);
            return dp[i][j];
        }
        int n = 1 + helper(i+1, j+1);  // replace
        n = min(n, 1 + helper(i+1, j));   // remove
        n = min(n, 1 + helper(i, j+1));  // insert
        dp[i][j] = n;
        return n;
    }
};

Links: leetcode-72-edit-distance

未经允许，禁止转载，本文源站链接：https://iamazing.cn/