※ 引述《DJYOMIYAHINA (通通打死)》之銘言： : class Node: : def __init__(self): : self.child = [None for _ in range(26)] : class Solution: : def minValidStrings(self, words: List[str], target: str) -> int: : # construct dict : root = Node() : for word in words: : cur = root : for c in word: : if cur.child[ord(c)-ord('a')] is None: : cur.child[ord(c)-ord('a')] = Node() : cur = cur.child[ord(c)-ord('a')] : dp = [10**9 for _ in range(len(target))] : dp.append(0) # dp[-1] = 0 : for i in range(len(target)): : cur = root : for j in range(i,len(target)): : if cur.child[ord(target[j])-ord('a')] is not None: : cur = cur.child[ord(target[j])-ord('a')] : dp[j] = min(dp[j], dp[i-1]+1) : else: : break : return -1 if dp[len(target)-1] == 10**9 else dp[len(target)-1] 其實我不太懂為啥這作法可以AC 題目給的 target 長度是 5 * 10^4 跑兩次 for loop 一定會爆的感覺 還是他測資剛好沒那麼極端每個都匹配到 因為提早break了所以不會跑到那麼多層= = 他跟 hard 那題長的幾乎一樣還是說 Medium 給的測資比較隨便? -- 你跟我說這個我有什麼辦法 https://i.imgur.com/wb5zrOy.jpeg -- ※ 發信站: 批踢踢實業坊(pttweb.org.tw), 來自: 122.100.73.13 (臺灣) ※ 文章網址: https://pttweb.org.tw/Marginalman/M.1726386914.A.322 https://leetcode.com/discuss/study-guide/1939806/rule-of-thumb-for-avoiding-tle