Leetcode # 712. Minimum ASCII Delete Sum for Two Strings

https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings

Failed Solution (Time Limit Exceeded)

讓我們來看看這個 solution 的 time complexity
O(len(s1) * len(s2) + min(len(s1), len(s2)) * len(s1) * len(s2))
= O(min(len(s1), len(s2)) * len(s1) * len(s2))
過於龐大，所以我們要修正做法使其 time complextity 降低

 

class Solution:
  def minimumDeleteSum(self, s1: str, s2: str) -> int:
    ascii_sum_1, ascii_sum_2 = sum([ord(c) for c in s1]), sum([ord(c) for c in s2])
    dp = []
    appeared_words = set()
    max_ascii_sum = 0
    for i1, c1 in enumerate(s1):
      for i2, c2 in enumerate(s2):
        if c1 == c2 and c1 not in appeared_words:
          appeared_words.add(c1)
          dp.append([ord(c1), [(i1, i2)], c1])
          max_ascii_sum = max(max_ascii_sum, ord(c1))

    while dp:
      ascii_sum, chars, word = dp.pop(0)
      for i1 in range(chars[-1][0] + 1, len(s1)):
        for i2 in range(chars[-1][1] + 1, len(s2)):
          if s1[i1] == s2[i2]:
            new_word = word + s1[i1]
            if new_word in appeared_words:
              continue
            appeared_words.add(new_word)
            new_ascii_sum = ascii_sum + ord(s1[i1])
            max_ascii_sum = max(max_ascii_sum, new_ascii_sum)
            dp.append([new_ascii_sum, 
                      chars + [(i1, i2)], 
                      new_word])
                      
    return ascii_sum_1 + ascii_sum_2 - max_ascii_sum * 2

Solution (DP, Bottom-Top, Optimized Space Complexity)

A(c) := ASCII value of character c ≡ ord(c)

C(i, j) ≡ computeCost(i, j)
:= the lowest ASCII sum of deleted characters
to make s1[:i] and s2[0:j] equal

≡

0
A(s2[j]) + C(i, j – 1)
A(s1[i]) + C(i – 1, j)
C(i – 1, j – 1)
min(A(s1[i]) + C(i – 1, j), A(s2[j]) + C(i, j – 1))

 if i < 0 and j < 0
if i < 0
if j < 0
if s1[i] == s2[j]
otherwise

當 i/j <0 表示 s1[0:i]/s2[0:j]不存在

  1. i, j < 0：
    兩個 str 都不存在 ⇒ 0
  2. i 或 j 其一 < 0：
    以 i < 0, j >= 0 舉例
    C(i, j) = sum([ord(c) for c in s[:j]])

    index 0 1 2 3 4 5 6 … j
    s1[:i] ✖︎ ✖︎ ✖︎ ✖︎ ✖︎ ✖︎ ✖︎ … ✖︎
    s2[:j] n e v e r g i   p
    A(s2[j]) 110 101 118 101 114 103 105   112
    C(i < 0, j >= 0) 110 110
    + 101
    = 211    		 211
    + 118
    = 329    		 329
    + 101
    = 430    		 430
    + 114
    = 544    		 544
    + 103
    = 647    		 647
    + 105
    = 752    		   1200
  3. s1[i] == s2 [j]：
    字元 s1[i] 和 s2[j] 沒有被移除的必要
    ⇒ C(i, j) ← C(i – 1, j – 1)
  4. s1[i] != s2 [j]：
    則選擇移除 s1[i] 或 s2[j]中
    造成 ASCII sum 增加幅度較小者
    ⇒ C(i, j) ← min(A(s1[i]) + C(i – 1, j), A(s2[j]) + C(i, j – 1))

讓我們來看看這個演算法是否合乎邏輯：

令 s1 = “delete”, s2 = “leet”

  s2[:0] = “l” s2[:1] = “le” s2[:2] = “lee” s2[:3] = “leet”
s1[:0] = “d” “” “” “” “”
s1[:1] = “de” “” “e” “e” “e”
s1[:2] = “del” “l” “l” “l” “l”
s1[:3] = “dele” “l” “le” “le” “le”
s1[:4] = “delet” “l” “le” “le” “let”
s1[:5] = “delete” “l” “le” “lee” “let”
  1. “d” 和 “leet” 沒有任何匹配的字元
    所以結果全是 “”
  2. “de” 和 “leet” 只有匹配 “e”
    所以結果全是 “e”
  3. “del” 和 “leet” 匹配了 “e” 和 “l”
    但 “el” 和 “le” 順序上的問題 
    “e” 和 “l” 只能擇一
    因為 “e” 的 ASCII code 較小
    所以結果全是 “l”
  4. “dele” 和 “l” 匹配的只有 “l”
    “dele” 和之後的 “le”, “lee”, “leet” 匹配了 “le”
  5. “delet” 和 “l” 匹配的只有 “l”
    “delet” 和之後的 “le”, “lee” 匹配了 “le”
    “delet” 和最後的 “leet” 匹配了 “let”
    (刪除了 “delet” 的 ”de“ 和 “leet” 的任意一個 ”e“)
  6. “delete” 和 “l” 匹配的只有 “l”
    “delete” 和 “le” 匹配了 “le”
    “delete” 和 “lee” 匹配了 “lee”
    “delete” 和最後的 “leet” 出現了選擇！

    1. “de le t e“, “lee t” ⇒ “lee“
    2. “de let e“, “le e t” ⇒ “let“

  由於 e 的 ASCII code 比較小，結果選擇了 “let”

如果字元 s2[j] 在 s1 中出現多次
如：s2[j] == s1[x] == s1[y]== s1[z], x < y < z
C(x, j), C(y, j), C(z, j) 則分別是選定將 (s1[x], s2[j]), (s1[y], s2[j]), (s1[z], s2[j])保留的結果
例：s1 = “ababa”, s2 = “bba”

  1. “a baba“, “bb a” ⇒ “a“
  2. “a ba ba“, “b ba” ⇒ “ba“
  3. “a b a ba“, “bba” ⇒ “bba“

 

Time Complexity: O(len(s1) * len(s2))
Space Complexity: O(min(len(s1), len(s2)))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def minimumDeleteSum(self, s1: str, s2: str) -> int:
    if len(s1) < len(s2):
      s1, s2 = s2, s1
    pre_dp = [0]
    ascii_sum = 0
    for c in s2:
      ascii_sum += ord(c)
      pre_dp.append(ascii_sum)
    for i in range(len(s1)):
      cur_dp = [ord(s1[i]) + pre_dp[0]]
      for j in range(len(s2)):
        value = (pre_dp[j]) \
                if s1[i] == s2[j] else \
                min(ord(s1[i]) + pre_dp[j + 1], 
                    ord(s2[j]) + cur_dp[j])
        cur_dp.append(value)
      pre_dp = cur_dp
        
    return cur_dp[-1]

 

Last Updated on 2023/08/24 by A1go

目錄

→ 目錄
Bitnami