• Leetcode 3213. Construct String with Minimum Cost
  • 1. 解題思路
  • 2. 代碼實現

• 題目鏈接：3213. Construct String with Minimum Cost

1. 解題思路

這一題的話思路上還是比較直接的，就是一個trie樹加一個動態規劃，通過trie樹來快速尋找每一個位置作為起點時能夠匹配的全部字符串，然后用一個動態規劃來獲取最優剪切方案。

其中，關于trie樹的內容可以參考我之前的博客《經典算法：Trie樹結構簡介》，這里就不過多展開了。

然后當前的實現其實還蠻暴力的，時間上勉勉強強通過了全部測試樣例，不過應該可以通過剪枝以及優化trie樹內的內容來進行一下優化，有興趣的讀者可以考慮一下其具體實現，這里就不過多進行展開了。

2. 代碼實現

給出python代碼實現如下：

class Trie:def __init__(self):self.trie = {}def add_word(self, word, cost):trie = self.triefor c in word:trie = trie.setdefault(c, {})if "eos" not in trie:trie["eos"] = (word, cost)elif cost < trie["eos"][1]:trie["eos"] = (word, cost)returndef find_all_prefix(self, word):prefixs = []trie = self.triefor c in word:if c not in trie:breaktrie = trie[c]if "eos" in trie:prefixs.append(trie["eos"])return prefixsclass Solution:def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:trie = Trie()for word, cost in zip(words, costs):trie.add_word(word, cost)n = len(target)ans = math.inf@lru_cache(None)def dp(idx):nonlocal ansif idx >= n:return 0prefixs = trie.find_all_prefix(target[idx:])if prefixs == []:return math.infreturn min(c + dp(idx+len(w)) for w, c in prefixs)ans = dp(0)return ans if ans != math.inf else -1

提交代碼評測得到：耗時10897ms，占用內存267.2MB。