勝肥肥寫個trie還寫的一坨了
哀
今天又是漬漬的一天
def replaceWords(self, dictionary: List[str], sentence: str) -> str:
class Node:
def __init__(self):
self.child = [None for _ in range(26)]
self.isEnd = False
root = Node()
# build
for v in dictionary:
cur = root
for c in v:
if cur.child[ord(c)-ord('a')] is None:
cur.child[ord(c)-ord('a')] = Node()
cur = cur.child[ord(c)-ord('a')]
else:
cur = cur.child[ord(c)-ord('a')]
cur.isEnd = True
# inference
words = sentence.split(' ')
ans = ""
for w in words:
cur = root
s_cur = ""
for c in w:
cur = cur.child[ord(c)-ord('a')]
if cur is None:
s_cur = w
break
else:
s_cur += c
if cur.isEnd == True:
break
ans += s_cur
ans += " "
return ans[:-1]