※ 引述《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 给的测资比较随便?