Repository navigation
Expand file tree
/
Copy pathreplace_words.py
More file actions
56 lines (45 loc) · 2.44 KB
/
Copy pathreplace_words.py
File metadata and controls
56 lines (45 loc) · 2.44 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
def replace_words(dictionary: list[str], sentence: str) -> str:
"""Replace Words.
Build a prefix trie from dictionary roots, then replace each sentence word with its shortest matching root.
In English, we have a concept called root, which can be followed by some other words to form another longer
word - let's call this word successor. For example, the root "an", followed by "other", can form another word
"another".
Now, given a dictionary consisting of many roots and a sentence, replace all the successors in the sentence
with the root forming it. If a successor has many roots that can form it, replace it with the root with the
shortest length. Output the sentence after the replacement.
Example: `dictionary = ["cat", "bat", "rat"]`, `sentence = "the cattle was rattled by the battery"` ->
`"the cat was rat by the bat"`
"""
words = sentence.split(" ")
prefix_trie = TrieNode()
for word in dictionary:
prefix_trie.insert(word)
return " ".join(prefix_trie.replace_word(word) for word in words)
class TrieNode:
"""A prefix trie node used to store dictionary roots and match sentence words against them."""
def __init__(self):
self.nodes: dict[str, TrieNode] = {}
def insert(self, word: str) -> None:
"""Insert word into the trie, stopping early if a shorter existing root already covers it."""
current_node = self
for index in range(1, len(word) + 1):
if current_node and word[:index] in current_node.nodes:
next_node = current_node.nodes[word[:index]]
if len(next_node.nodes) == 0:
return
if index == len(word):
current_node.nodes[word[:index]] = TrieNode()
return
current_node = next_node
elif current_node:
current_node.nodes.setdefault(word[:index], TrieNode())
current_node = current_node.nodes.get(word[:index])
def replace_word(self, word: str) -> str:
"""Walk the trie along word's prefixes and return the shortest matching root, or word unchanged."""
current_node = self
for index in range(1, len(word) + 1):
if current_node and word[:index] in current_node.nodes:
current_node = current_node.nodes[word[:index]]
if len(current_node.nodes) == 0:
return word[:index]
return word