这题要将某个prefix开头的词（successor）替换成这个prefix（root），我觉得这道题在极端条件下似乎使用字典树会快一些吧，但是我就尝试了下把那个prefix放到hashset里面，然后对于每个词一一根据前缀一一尝试，反正通过了，我就没往下了
题目设置的有点宽，我连root length都没优化都能ac，就先这样吧，要是不能ac了再改成字典树吧
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
class Solution(object):
def replaceWords(self, dict, sentence):
"""
:type dict: List[str]
:type sentence: str
:rtype: str
"""
root_dict = set(dict)
raws = sentence.split()
res = []
for raw in raws:
flag = False
for i in range(0,len(raw)):
prefix = raw[0:i+1]
if prefix in root_dict:
res.append(prefix)
flag = True
break
if flag == False:
res.append(raw)
return ' '.join(res)
