LC 0648 [M] Replace Words - ALawliet/algorithms GitHub Wiki
use the first word found and make sure it is not revisited (set or first in trie)
search prefixes directly
class Solution:
def replaceWords(self, dictionary: List[str], sentence: str) -> str:
rootset = set(dictionary)
def replace(word):
for i in range(1, len(word)):
if word[:i] in rootset:
return word[:i]
return word
return " ".join(map(replace, sentence.split()))
trie
class Node:
def __init__(self):
self.sub = collections.defaultdict(Node)
#here should have a isend attribute, we store the word instead.
self.word = None
class Trie:
def __init__(self):
self.root = Node()
def insert(self, word):
cur = self.root
for i in word: cur = cur.sub[i]
cur.word = word
def find(self, word):
cur = self.root
for i in word:
#this means this sentence word has no 'root'
if i not in cur.sub: return word
cur = cur.sub[i]
if cur.word is not None: return cur.word
#cannot find a matched root for current word
return word
class Solution:
def replaceWords(self, dict: List[str], sentence: str) -> str:
roots = Trie()
for word in dict: roots.insert(word)
return ' '.join(roots.find(word) for word in sentence.split())