Leetcode 3291. Minimum Number of Valid Strings to Form Target I

• Leetcode 3291. Minimum Number of Valid Strings to Form Target I
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3291. Minimum Number of Valid Strings to Form Target I

1. 解题思路

这一题第一反应就是用一个字典树+动态规划的方式，倒是也搞定了，不过对于下一题就搞不定了，感觉还是得进一步优化一下，不过对这道题倒是也算ok了。

2. 代码实现

给出python代码实现如下：

class Trie:def __init__(self):self.trie = {}def add_word(self, word):trie = self.triefor c in word:trie = trie.setdefault(c, {})trie["eos"] = ""def find(self, word):trie = self.triefor c in word:if c not in trie:return Falsetrie = trie[c]return "eos" in trieclass Solution:def minValidStrings(self, words: List[str], target: str) -> int:trie = Trie()for w in words:trie.add_word(w)n = len(target)@lru_cache(None)def dp(idx):if idx >= n:return 0_trie = trie.trieans = math.infwhile idx < n and target[idx] in _trie:_trie = _trie[target[idx]]idx += 1ans = min(ans, 1+dp(idx))return ansans = dp(0)return ans if ans != math.inf else -1

提交代码评测得到：耗时12771ms，占用内存41.8MB。