LeetCode Daily Question 13

3 月 18 日 每日一题

题目：Prefix Replacement

Prefixes are words that can be followed by other letters to form a longer word — let’s call this final, combined word the successor. For example, the prefix “an” followed by the word “other” forms the word “another.” Here, “an” is the prefix and “another” is the successor.
Given a dictionary consisting of many prefixes and a sentence, you need to replace all the successors in the sentence with the prefix forming it. If a successor has many prefixes that can form it, replace it with the prefix with the shortest length.
The input will only have lower-case letters. Return the new sentence in a vector of strings.

1
2
3

Example:
Prefixes: ["cat", "bat", "rat"]
Sentence: ["the", "cattle", "was", "rattled", "by", "the", "battery"] Output: ["the", "cat", "was", "rat", "by", "the", "bat"]

mplementation: Your solution must run in O(PM + NM^2) time, where P represents the number of prefixes in the prefix vector, N represents the number of words in the sentence vector, and M represents the length of the longest string in the sentence vector.

思路

今天这道题来自 281lab 的 handwritten problem。 基本思路是利用 set 存储 prefix。遍历每一个 word 的每一个 character，如果可以在 set 里找到对应 prefix 则 push，prefix，否则 push 原本的 word。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

vector<string> replace_words(const vector<string>& prefixes,
                             const vector<string>& sentence) {
  // TODO
    unordered_set<string> pref;
    vector<string> res;
    for(auto prefix: prefixes){
        pref.insert(prefix);
    }
    for(auto word: sentence){
        bool isInsert = true;
        string temp = "";
        for(auto character: word){
            temp += character;
            if(pref.count(temp)){
                res.push_back(temp);
                isInsert = false;
                break;
            }
        }
        if(isInsert)
            res.push_back(word);
    }
  return res;
}