LeetCode 583 Delete Operation for Two Strings

    
        标签：
        
            动态规划问题
        
            LeetCode
        
    发布于：2022-02-16 14:09:35
    编辑于：2022-02-16 14:46:19
    浏览量：867

概述

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

Links: leetcode-583-delete-operation-for-two-strings