Leetcode # 664. Strange Printer

https://leetcode.com/problems/strange-printer

Solution (DP, Bottom-Top) 

Dynamic Programming

dp[l][r] := The minimum number of operations needed
to transform  [s[r]] * (r - l + 1) into s[l:r + 1]
=

if all(c = s[r] for c in s[l:r]):
1. 0
2. 1
else:
1. min([1 + dp[j][i] + dp[i + 1][r] for i in range(j, r)])
2. min([dp[j][i] + dp[i + 1][r] for i in range(j, r)])
j := j ∈ [l, r] and s[j] != s[r]
∀ k ∈ ℕ and k ∈ [l, j), s[k] == s[r]
return :=  1. dp[0][len(s) - 1] + 1
2. dp[0][len(s) - 1]
  • 方案 1 ：
    dp[l][r] 並不包含首字母 s[l] 印刷的那一次
    所以當 l == r ，dp[l][r] → 0
    當 s[l:r + 1] 拆解為 s[l:j] + s[j:i] + s[i + 1:r + 1] 時
    要補上 s[l:r + 1] (首字母 s[l]) 和 s[j:i] (首字母s[j]，且 s[l] != s[j] 必定成立)
    s[l] 和 s[j] 相差的那一次
  • 方案 2 ：
    dp[l][r] 包含首字母印刷的那一次
    所以當 l == r ，dp[l][r] → 1
    當 s[l:r + 1] 拆解為 s[l:j] + s[j:i] + s[i + 1:r + 1] 時
    直接取 dp[j][i] + dp[i + 1][r] 即可

Time Complexity: O(len(s) ** 3)
Space Complexity: O(len(s) ** 2)
(The input and output generally do not count towards the space complexity.)

方案 1

class Solution:
  def strangePrinter(self, s: str) -> int:
    dp = [[len(s)] * len(s) for c in s]
    for length in range(1, len(s) + 1):
      for l in range(len(s) - length + 1):
        j = None
        r = l + length - 1
        for i in range(l, r):
          if j is None:
            if s[i] == s[r]:
              continue
            j = i
          dp[l][r] = min(dp[l][r], 
                         1 + dp[j][i] + dp[i + 1][r])
        
        if j is None: dp[l][r] = 0
    return dp[0][len(s) - 1] + 1

注意！在 Python 中 0 視作 False
⇒ if not j:
if j is None:

方案 2

class Solution:
  def strangePrinter(self, s: str) -> int:
    dp = [[len(s)] * len(s) for c in s]
    for length in range(1, len(s) + 1):
      for l in range(len(s) - length + 1):
        j = None
        r = l + length - 1
        for i in range(l, r):
          if j is None:
            if s[i] == s[r]:
              continue
            j = i
          dp[l][r] = min(dp[l][r], 
                         dp[j][i] + dp[i + 1][r])
        
        if j is None: dp[l][r] = 1
    return dp[0][len(s) - 1]

 

錯誤分析

正確的印刷順序

例：s ← "ccdcadbddbaddcbccdcdabcbcddbccdcbad"

用括號來表示正確的印刷順序會變成：
(cc)(d(c)(a)d(b)dd(b)(a)dd(c(b)cc)d(c)d(a(b(c)b(c)(dd)b(cc(d)c)b)a)d)

我們取 bcbcddbccdcb 來說明
正確的印刷順序是 (b(c)b(c)(dd)b(cc(d)c)b)

即 s[21, 32](bcbcddbccdcb)
→ [21](b) [22](c) [23:32](bcddbccdcb)
→ [21](b) [22](c) [23](b) [24](c) [25:32](ddbccdcb)
→ [21](b) [22](c) [23](b) [24](c) [25:26](dd) [27:32](bccdcb)
→ [21](b) [22](c) [23](b) [24](c) [25:26](dd) [28](b) [28:31](ccdc) [32](b)

我原先的演算法

我原先的演算法
令 si 能拆解為 si[0] + (si[0] * a) + si + 1, 1 + (si[0] * b) + si + 1, 2
strange_printer(si) := 1 + strange_printer(si + 1, 1) + strange_printer(si + 1, 2)
然而這只顧慮到開頭的(連續) si[0] 字元
以及最後一組(連續) si[0] 字元
忽略了中間剩下的 si[0] 也能在同一次印刷中被處理的可能性

比較

以上述的 bcbcddbccdcb 為例
正確的印刷順序為 (b(c)b(c)(dd)b(cc(d)c)b) (共印刷 6 次)
而我原先的演算法卻是 (b(c(b(c)(dd)b)(cc(d)c))b) (共印刷 7 次)
可以看到中間 bcddb 頭尾的 b
在正確的順序是和頭尾的 b 一起印出來
而我原先的演算法則是另外再多印了 1 次

Last Updated on 2023/08/16 by A1go

目錄

→ 目錄
Bitnami