LeetCode 583 Delete Operation for Two Strings

Tag: 动态规划问题 LeetCode Posted on 2022-02-16 14:09:35 Edited on 2022-02-16 14:46:19 Views: 167

概述

https://leetcode.com/problems/delete-operation-for-two-strings/

动态规划法

极值问题,无脑动态规划。

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size(), vector<int>(word2.size(), -1));
        return helper(dp, word1, word2, 0, 0);
    }
    
    int helper(vector<vector<int>>& dp, string& word1, string& word2, 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(dp, word1, word2, i+1, j+1);
        } else {
            dp[i][j] = min(1 + helper(dp, word1, word2, i, j + 1), 1 + helper(dp, word1, word2, i + 1, j));
        }
        return dp[i][j];
    }
};

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