做网站的书籍,wordpress 标题 插件,怎么做带数据库的网站,天津网站建设服务Leetcode 3291. Minimum Number of Valid Strings to Form Target I 1. 解题思路2. 代码实现 题目链接#xff1a;3291. Minimum Number of Valid Strings to Form Target I
1. 解题思路
这一题第一反应就是用一个字典树动态规划的方式#xff0c;倒是也搞定了#xff0c…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, 1dp(idx))return ansans dp(0)return ans if ans ! math.inf else -1提交代码评测得到耗时12771ms占用内存41.8MB。
