LeetCode 72 Edit Distance

标签: 动态规划问题 发布于:2022-02-15 15:18:16 编辑于:2022-02-15 16:46:48 浏览量:376

概述

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;
    }
};

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