Re: [閒聊] 每日leetcode

看板Marginalman作者dont (dont)時間1年前 (2024/08/21 15:33)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串746/1548 (看更多)

664. Strange Printer ## 思路印aaabbaaa的次數 = 印aba的次數 = 印ab的次數先把連續重複的合起來 aaabbaaa -> aba dp[left][right] = 範圍內最少print的次數如果s[left] 跟 s[right] 字元一樣, 就回傳 dp[left][right-1] 不然就是在範圍內找k (s[left] == s[k]) 切割成兩個substring ## Complexity Time: O(N^3) Space: O(N^2) ## Code Recursion ```python class Solution: def strangePrinter(self, s: str) -> int: s = [ch for i, ch in enumerate(s) if i == len(s) -1 or ch != s[i+1]] n = len(s) @cache def dp(left, right): if left > right: return 0 if left == right: return 1 if s[left] == s[right]: return dp(left, right-1) res = float('inf') for k in range(left, right): if s[left] == s[k]: res = min(res, dp(left, k) + dp(k+1, right)) return res return dp(0, n-1) ``` Iteration ```python class Solution: def strangePrinter(self, s: str) -> int: s = [ch for i, ch in enumerate(s) if i == len(s) -1 or ch != s[i+1]] n = len(s) dp = [[float('inf')] * n for _ in range(n)] for i in range(n): dp[i][i] = 1 for left in range(n-1, -1, -1): for right in range(left+1, n): if s[left] == s[right]: dp[left][right] = dp[left][right-1] else: for k in range(left, right): if s[left] == s[k]: dp[left][right] = min(dp[left][right], dp[left][k] + dp[k+1][right]) return dp[0][-1] ``` -- http://i.imgur.com/OLvBn3b.jpg