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]
}
Golang - Previous
647. Palindromic Substrings
Next - Golang
649. Dota2 Senate
Last modified 6mo ago