Problem statement

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

Solution

Although this is the fourth problem of leetcode weekly contest 42, the solution is pretty straightforward.

The best solution should employ the trie tree, by now, I have no idea of that. Alternatively, I add all root words into a hash table and search by the key value.

The general idea:

Add all roots into hash table.
Separate the strings into single word.
Search from the start of each word to find if root exists in hash table.

Time complexity is O(n), n is the size of setence, space complexity is O(n + m), m is the size of root.

class Solution {

public:

    string replaceWords(vector<string>& dict, string sentence) {

        // add the dict into a set to search

        set<string> ht;

        for(auto dic : dict){

            ht.insert(dic);

        }

        // partition the sentences into words

        vector<string> words;

        for(int i = , j = ; i < sentence.size() && j <= sentence.size(); j++){

            if(sentence[j] == ' ' || j == sentence.size()){

                words.push_back(sentence.substr(i, j - i));

                i = j + ;

            }

        }

        // find root in dictionary

        for(int i = ; i < words.size(); i++){

            for(int j = ; j < words[i].size(); j++){

                if(ht.find(words[i].substr(, j + )) != ht.end()){

                    words[i] = words[i].substr(, j + );

                    break;

                }

            }

        }

        // build the whole sentence

        string ans = words[];

        for(int i = ; i < words.size(); i++){

            ans += " " + words[i];

        }

        return ans;

    }

};

巴特西

648. Replace Words

Problem statement

Solution

最新文章

热门文章