# LeetCode: 648. 单词替换¶

## 1、题目描述¶

输入: dict(词典) = ["cat", "bat", "rat"]
sentence(句子) = "the cattle was rattled by the battery"



• 输入只包含小写字母。
• 1 <= 字典单词数 <=1000
• 1 <= 句中词语数 <= 1000
• 1 <= 词根长度 <= 100
• 1 <= 句中词语长度 <= 1000

## 2、解题思路¶

• 字典树
class Trie:

def __init__(self):
"""
"""

def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
for i in word:
if cur.get(i) is None:
cur[i] = {}
cur = cur[i]
if cur.get("end") is None:
cur["end"] = 1

def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
for i in word:
if i not in cur:
return False
cur = cur[i]

if cur.get("end") is not None:
return True
else:
return False

def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
for i in prefix:
if i not in cur:
return False
cur = cur[i]

return True

class Solution:
def replaceWords(self, dict: List[str], sentence: str) -> str:
trie = Trie()
for d in dict:
trie.insert(d)

temp = sentence.split()

for index, word in enumerate(temp):
for i in range(1, len(word)):
if trie.search(word[:i]):
temp[index] = word[:i]
break
return " ".join(temp)

• 哈希表
class Solution:
def replaceWords(self, dict: List[str], sentence: str) -> str:

mapping = set(dict)

temp = sentence.split()

for index, word in enumerate(temp):
for i in range(1, len(word)):
if word[:i] in mapping:
temp[index] = word[:i]
break
return " ".join(temp)