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
把字典转成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: }
No comments:
Post a Comment