648. Replace Words

Posted on Edited on In

648. Replace Words

Description

Difficulty: Medium

Related Topics: Array, Hash Table, String, Trie

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:

1
2
Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Example 2:

1
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.

Hints/Notes

  • Trie

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    struct TrieNode{
        bool end;
        vector<TrieNode*> children;
        TrieNode() {
            end = false;
            children = vector<TrieNode*>(26, nullptr);
        }
    };

    string replaceWords(vector<string>& dictionary, string sentence) {
        TrieNode* root = new TrieNode();
        for (string word : dictionary) {
            TrieNode* head = root;
            for (char c : word) {
                if (!head->children[c - 'a']) {
                    head->children[c - 'a'] = new TrieNode();
                }
                head = head->children[c - 'a'];
            }
            head->end = true;
        }
        size_t pos = 0;
        string word;
        istringstream iss(sentence);
        string res;
        do {
            string word;
            iss >> word;
            if (word == "") {
                break;
            }
            TrieNode* head = root;
            string newWord;
            for (char c : word) {
                if (!head) {
                    newWord = word;
                    break;
                } else {
                    if (head->end) {
                        break;
                    } else {
                        head = head->children[c - 'a'];
                        newWord += c;
                    }
                }
            }
            res = res == "" ? newWord : res + " " + newWord;
        } while (iss);
        return res;
    }
};