※ 引述《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 給的測資比較隨便?