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

10**5以下都可以n**2ㄅ 忘记哪看到的

我怎么记得 10^3 才可以= =

真假 有那么小ㄇ 我印象不少10**4我用n**2会过

有时候是题目测资没给那么极端比如排序算法那题之前随便写的快排会过后来他加入一个超极端CASE 之后就不能乱写了

原来 那我以前搞错了

下次我不到10^5都撞撞看好了 反正不撞也没分:(