🟨兩字串的最小ASCII刪除和

本題取自 Leetcode 712. Minimum ASCII Delete Sum for Two Strings

題目

Given two strings s1 and s2, return the lowest ASCII sum of deleted characters to make two strings equal.

Example 1:

Input: s1 = "sea", s2 = "eat"
Output: 231
Explanation: Deleting "s" from "sea" adds the ASCII value of "s" (115) to the sum.
Deleting "t" from "eat" adds 116 to the sum.
At the end, both strings are equal, and 115 + 116 = 231 is the minimum sum possible to achieve this.


Example 2:

Input: s1 = "delete", s2 = "leet"
Output: 403
Explanation: Deleting "dee" from "delete" to turn the string into "let",
adds 100[d] + 101[e] + 101[e] to the sum.
Deleting "e" from "leet" adds 101[e] to the sum.
At the end, both strings are equal to "let", and the answer is 100+101+101+101 = 403.
If instead we turned both strings into "lee" or "eet", we would get answers of 433 or 417, which are higher.
 

Constraints:

1 <= s1.length, s2.length <= 1000
s1 and s2 consist of lowercase English letters.

分析

題目要求在s1、s2當中刪去若干字母使得兩字串剩下的部分相同，並且求刪除的字母轉為ASCII字碼的數字總和最小值。

Python3要取得字母char的ASCII碼可以使用ord(char)。

如果把本題要求最小的「刪除字母的ASCII總和」，改成「刪除字母字數」，會發現所得的字串其實就是前面介紹過的LCS。

換言之，本題可以使用和LCS類似的狀態與轉移式，只是判斷最小值時要加上權重。

分治法

子問題可以這樣描述：

對於給定的i1,i2，求s1[i1:]和s2[i2]的最小ASCII刪除和。

設計狀態、找出轉移式與最小問題

狀態：以solve(i1, i2)：表示s1[i1:]和s2[i2:]的最小ASCII刪除和。

轉移式：首先要比較 s1[i1]和s2[i2]是否相同。

若s1[i1] == s2[i2]：

solve(i1,i2) = solve(i1+1,i2+1)

和LCS相似的貪心(Greedy)思維可以得出，兩邊都不刪除即為最佳，故繼續比較s1[i1+1]和s2[i2+1]

若s1[i1] != s2[i2]：

兩字母必定至少刪除其中一個。因此

solve(i1,i2) = min(
    ord(s1[i1]) + solve(i1+1, i2),  # 刪除s1[i1]
    ord(s2[i2]) + solve(i1, i2+1)   # 刪除s2[i2]
)

實作

Top-Down DP

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        @cache 
        def solve(i1, i2):
            if i1 == len(s1):
                return sum(ord(c) for c in s2[i2:])
            if i2 == len(s2):
                return sum(ord(c) for c in s1[i1:])
            if s1[i1] == s2[i2]:
                return solve(i1+1, i2+1)
            return min(
                ord(s1[i1]) + solve(i1+1, i2),
                ord(s2[i2]) + solve(i1, i2+1)
            )
        return solve(0,0)

Bottom-Up DP

和top-down類似，本例為了讓計算順序從小到大，定義狀態dp[i][j]為s1[:i]與s2[:j]。因此轉移式和top-down略有不同。

和前面矩陣題型一樣，加入了最上面一列與最左邊一行當作邊界條件。

class Solution:
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        dp = [[0]*(len(s2)+1) for _ in range(len(s1)+1)]
        for i1 in range(len(s1)):
            dp[i1+1][0] = ord(s1[i1])+dp[i1][0]
        for i2 in range(len(s2)):
            dp[0][i2+1] = ord(s2[i2])+dp[0][i2]
        for i1 in range(len(s1)):
            for i2 in range(len(s2)):
                if s1[i1]==s2[i2]:
                    dp[i1+1][i2+1] = dp[i1][i2]
                else:
                    dp[i1+1][i2+1] = min(
                        ord(s1[i1])+dp[i1][i2+1],
                        ord(s2[i2])+dp[i1+1][i2],
                    )
        for row in dp: print(row)
        return dp[-1][-1]

複雜度分析

時間複雜度

時間複雜度 = 狀態轉移數 x 計算複雜度

本題的狀態數 = O(n x m)，n、m分別為word1、word2的長度

計算複雜度為O(1)

因此總時間複雜度 = O(n x m)

空間複雜度

空間複雜度＝狀態數＝ O(n x m)

若採用Rolling Bottom Up DP的技巧，則降低一個維度，空間複雜度＝ O(n)

結語

還記得我在Leetcode上初見這些字串題時，只覺得每一題的拆解邏輯都不同、相當複雜。不過，深入學習之後，還是能找到一些共同點。例如都以字串的index作為狀態、從字串匹配的規則推論狀態轉移式…特別是day 11 LCS的解題邏輯，在字串題當中有相當大的應用空間，若讀者對於字串題不知如何下手可以多熟悉這個題型。

以上為Day14的內容！感謝你的閱讀，如果有不同的想法或心得，歡迎留言一同討論！

本文也同步登載在我的個人部落格，記錄我的學習筆記與生活點滴，歡迎來逛逛。

明天會再看本系列的最後一題字串例題，同時也會是我們首次挑戰Hard題，敬請期待！

[2024鐵人賽系列文] Python刷題小白的30日動態規劃之旅－Day 14 字串題型(六) 兩字串的最小ASCII刪除和

目錄