LeetCode 712. 两个字符串的最小ASCII删除和

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

✅ 712. 两个字符串的最小 ASCII 删除和

思路分析

解法一：动态规划（推荐）

核心思路：

dp[i][j] 表示使 s1[i:] 与 s2[j:] 相等的最小删除 ASCII 和。

若字符相等则继承 dp[i+1][j+1]，否则取删除一边的最小代价。

自底向上填表。

复杂度分析：

时间复杂度：O(mn)，其中 m、n 为字符串长度。

空间复杂度：O(mn)。

class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = m - 1; i >= 0; i--) {
            dp[i][n] = dp[i + 1][n] + s1.charAt(i);
        }
        for (int j = n - 1; j >= 0; j--) {
            dp[m][j] = dp[m][j + 1] + s2.charAt(j);
        }

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    dp[i][j] = dp[i + 1][j + 1];
                } else {
                    int del1 = s1.charAt(i) + dp[i + 1][j];
                    int del2 = s2.charAt(j) + dp[i][j + 1];
                    dp[i][j] = Math.min(del1, del2);
                }
            }
        }

        return dp[0][0];
    }
}

func minimumDeleteSum(s1 string, s2 string) int {
	m := len(s1)
	n := len(s2)
	dp := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		dp[i] = make([]int, n+1)
	}

	for i := m - 1; i >= 0; i-- {
		dp[i][n] = dp[i+1][n] + int(s1[i])
	}
	for j := n - 1; j >= 0; j-- {
		dp[m][j] = dp[m][j+1] + int(s2[j])
	}

	for i := m - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			if s1[i] == s2[j] {
				dp[i][j] = dp[i+1][j+1]
			} else {
				del1 := int(s1[i]) + dp[i+1][j]
				del2 := int(s2[j]) + dp[i][j+1]
				if del1 < del2 {
					dp[i][j] = del1
				} else {
					dp[i][j] = del2
				}
			}
		}
	}

	return dp[0][0]
}

相似题目

题目	难度	考察点
1143. 最长公共子序列	中等	DP
583. 两个字符串的删除操作	中等	DP
72. 编辑距离	困难	DP
516. 最长回文子序列	中等	DP
97. 交错字符串	中等	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/23358158