648. Replace Words

Medium
​
In English, we have a concept called root, which can be followed by some other word to form another longer word - let's call this word successor. For example, when the root "an" is followed by the successor word "other", we can form a new word "another".
Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the successors in the sentence with the root forming it. If a successor can be replaced by more than one root, replace it with the root that has the shortest length.
Return the sentence after the replacement.
Example 1:
Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output:
"the cat was rat by the bat"
Example 2:
Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output:
"a a b c"
Constraints:
  • 1 <= dictionary.length <= 1000
  • 1 <= dictionary[i].length <= 100
  • dictionary[i] consists of only lower-case letters.
  • 1 <= sentence.length <= 106
  • sentence consists of only lower-case letters and spaces.
  • The number of words in sentence is in the range [1, 1000]
  • The length of each word in sentence is in the range [1, 1000]
  • Every two consecutive words in sentence will be separated by exactly one space.
  • sentence does not have leading or trailing spaces.

解題

Runtime: 152 ms, faster than 40.42%
Memory Usage: 15.9 MB, less than 78.72%
func replaceWords(dictionary []string, sentence string) string {
m := make(map[string]bool)
for _, word := range dictionary {
m[word] = true
}
words := strings.Fields(sentence)
ans := ""
for _, word := range words {
for i:=1; i<len(word)+1; i++ {
if m[word[:i]] {
ans = ans + word[:i] + " "
break
}
if i == len(word) {
ans = ans + word + " "
}
}
}
return ans[:len(ans)-1]
}