→ DJYOSHITAKA: 大師 09/23 20:00
推 sixB: 大師 09/23 20:22
2707. Extra Characters in a String
## 思路
對dictionary建TrieTree再用recursion dp
不過不用Trie,
直接把dictionary轉成set, 再判斷s[i:j]好像也可以過
## Code
```python
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
class TrieTree:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
curr = self.root
for ch in word:
if ch not in curr.children:
curr.children[ch] = TrieNode()
curr = curr.children[ch]
curr.is_word = True
class Solution:
def minExtraChar(self, s: str, dictionary: List[str]) -> int:
trie = TrieTree()
for word in dictionary:
trie.insert(word)
n = len(s)
@cache
def dp(i):
if i == n:
return 0
# skip
res = 1 + dp(i+1)
curr = trie.root
for j in range(i, n):
if s[j] not in curr.children:
break
curr = curr.children[s[j]]
if curr.is_word:
res = min(res, dp(j+1))
return res
return dp(0)
```
--
https://i.imgur.com/kyBhy6o.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.30.190 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1727088572.A.489.html