[Leetcode] Replace Words, Solution

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 rootforming 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:

1. The input will only have lower-case letters.
2. 1 <= dict words number <= 1000
3. 1 <= sentence words number <= 1000
4. 1 <= root length <= 100
5. 1 <= sentence words length <= 1000

[Thoughts]
把字典转成hashmap，这样查询节省时间。这里用stringstream来读取子字符串，然后在子字符串中处理prefix，第一个被查到的就是最短的那个。

很简单的一道题。可说的东西不多。


[Code]

1:    string replaceWords(vector<string>& dict, string sentence) {  
2:      if(dict.size() == 0) return sentence;  
3:      unordered_map<string, int> roots;  
4:      for(auto& root : dict) {  
5:        roots[root] = 1;  
6:      }  
7:        
8:      string result = "";  
9:        
10:      stringstream ss(sentence);  
11:      string successor ;  
12:      while(ss>>successor ) {  
13:          
14:        string prefix;  
15:        for(int i =1; i<= successor.size(); i++) {  
16:          prefix = successor.substr(0, i);  
17:          if(roots.find(prefix) != roots.end()) break;  
18:        }  
19:          
20:        result += prefix + " ";  
21:      }  
22:        
23:      //remove the end empty space  
24:      if (result != "") result.resize(result.size()-1);  
25:      return result;  
26:    }