Implement typeahead. Given a string and a dictionary, return all words that contains the string as a substring. The dictionary will give at the initialize method and wont be changed. The method to find all words with given substring would be called multiple times.

Have you met this question in a real interview?

Yes

Example

Given dictionary ={"Jason Zhang", "James Yu", "Bob Zhang", "Larry Shi"}

search"Zhang", return["Jason Zhang", "Bob Zhang"].

search"James", return["James Yu"].

class Typeahead {
private:
    map<string, vector<int>> mp;
    vector<string> strs;
public:
    // @param dict: A dictionary of words dict
    Typeahead(unordered_set<string> &dict) {
        // do initialize if necessary
        int cnt = 0;
        for (auto& str : dict) {
            strs.push_back(str);
            int len = str.length();
            for (int i = 0; i < len; ++i) {
                for (int j = i + 1; j <= len; ++j) {
                    string tmp = str.substr(i, j - i);
                    if (mp.find(tmp) == mp.end()) {
                        mp[tmp] = {cnt};
                    } else {
                        if (mp[tmp][mp[tmp].size() - 1] != cnt) {
                            mp[tmp].push_back(cnt);
                        }
                    }
                }
            }
            ++cnt;
        }
    }

    // @param str: a string
    // @return a set of words
    vector<string> search(string &str) {
        // Write your code here
        vector<string> res;
        if (mp.find(str) == mp.end()) {
            return res;
        } else {
            for (auto idx : mp[str]) {
                res.push_back(strs[idx]); 
            }
        }
        return res;
    }
};