今天的不會 借用大師的答案
※ 引述《DJYOMIYAHINA (通通打死)》之銘言：
: 看著安沙寫的 還是沒能想到
: dp(i,j) -> s[i:j]的答案
: 每次更新的時候遍歷 for k in [i+1,j]
: 若 s[k] = s[i]
: 則可以試著一次打印i:k as s[i]
: 然後加上dp(i,k-1)+dp(k+1,j)
: 因為這時s[i:k-1]以及s[k+1,j]還沒有打印好
: 我們只是先決定要打印一排s[i]
: 就根據這個規則遍歷下去
: 每次dp(i,j)，就遍歷i,j中間的character一次
: 然後稍微memorize一下
: 我其實只會寫recursive
: 要我bottom-up我反而完全不會寫
: def strangePrinter(self, s: str) -> int:
: n = len(s)
: dp_mem = [[-1 for _ in range(n)] for _ in range(n)]
: #init
: for i in range(n):
: dp_mem[i][i] = 1
: def dp(i,j):
: if j<i:
: return 0
: elif dp_mem[i][j] != -1:
: return dp_mem[i][j]
: cur_dp_val = 1+dp(i+1,j)
: for k in range(i+1,j+1):
: if s[k] == s[i]:
: cur_dp_val = min(cur_dp_val, dp(i,k-1)+dp(k+1,j))
: dp_mem[i][j] = cur_dp_val
: return cur_dp_val
: return dp(0,n-1)
自己的答案就用for迴圈 但只對了前100個測資 後面100個過不了
class Solution:
def strangePrinter(self, s: str) -> int:
d = defaultdict(list)
# 先找出每個字母所在位置
for i, v in enumerate(s):
d[v].append(i)
word = [' '] * len(s)
current = ans_1 = 0
for _ in range(len(s)):
w = s[_]
if word[_] = s[_]:
continue
idxs = d[w]
curr = []
# 由左至右 畫當前位置到每個同字母 所對應的正確字母數
# 原本只找同字母最遠的 但不夠只好全部都跑一遍
for idx in idxs:
cp = word[:]
cp[_:idx+1] = w * (idx+1-_)
cu = sum(1 for x in range(len(cp)) if cp[x] == s[x])
if cu > current:
curr.append((cu, idx))
# 選最大正確數中最近的idx
current, ix = min(curr, key=lambda x: (-x[0], x[1]))
word[_:ix+1] = cp[_:ix+1]
ans_1 += 1
# 發現反算會得到更少次數 如 tbgtgb 依樣照葫蘆
word = [' '] * len(s)
current = ans_2 = 0
for _ in range(len(s)-1, -1, -1):
w = s[_]
if word[_] == s[_]:
continue
idxs = d[w][::-1]
curr = []
for idx in idxs:
cp = word[:]
cp[idx:_+1] = w * (_+1-idx)
cu = sum(1 for x in range(len(cp)) if cp[x] == s[x])
if cu > current:
curr.append((cu, idx))
current, ix = min(curr, key=lambda x: (-x[0], x[1]))
word[ix:_+1] = cp[ix:_+1]
ans_2 += 1
return ans_1 if ans_1 < ans_2 else ans_2
其實在一開始自己找測資時就遇到不符合的答案了 但我真不會dp 漬