题目描述:
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
, which can form another word another
.
Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor
in the sentence with the root
forming it. If a successor
has many roots
can form it, replace it with the root with the shortest length.
You need to output the sentence after the replacement.
Example 1:
Input: dict = ["cat", "bat", "rat"] sentence = "the cattle was rattled by the battery" Output: "the cat was rat by the bat"
Note:
- The input will only have lower-case letters.
- 1 <= dict words number <= 1000
- 1 <= sentence words number <= 1000
- 1 <= root length <= 100
- 1 <= sentence words length <= 1000
题目大意:
英文中,以较短的单词为前缀,可以构成较长的单词。此时前缀可以称为“词根”。
给定一组词根字典dict,一个句子sentence。将句中的单词换为字典中出现过的最短词根。
解题思路:
字典树(Trie)
利用词根dict构建字典树trie,遍历sentence中的word,在trie中进行搜索。
Python代码:
class TrieNode:
def __init__(self):
self.children = dict()
self.isWord = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for letter in word:
child = node.children.get(letter)
if child is None:
child = TrieNode()
node.children[letter] = child
node = child
node.isWord = True
def search(self, word):
ans = ''
node = self.root
for letter in word:
node = node.children.get(letter)
if node is None: break
ans += letter
if node.isWord: return ans
return word
class Solution(object):
def replaceWords(self, dict, sentence):
"""
:type dict: List[str]
:type sentence: str
:rtype: str
"""
trie = Trie()
for word in dict: trie.insert(word)
ans = []
for word in sentence.split():
ans.append(trie.search(word))
return ' '.join(ans)
本文链接:http://bookshadow.com/weblog/2017/07/24/leetcode-replace-words/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。