LintCode-231: Typeahead (System Design題)

此題考察對map的應用。

map < string, vector > wordMap;

記錄每個subWord對應的dict中的名字。

vector words;

把dict中的名字按順序記下來，友善search()傳回。

注意去重。有兩種去重的情況。

一個是dict裡面單個名字出現兩個同樣的字母或同樣的單詞時，比如說tree，或”Yang Yang”。這種情況通過

if (wordMap[subWord][vecSize - 1] != index)

來去重。

另一種情況是dict裡面出現兩個一樣的名字，比如說”James Wang”, “James Wang”，這種情況map自身就能去重。

class Typeahead {
public:
    /*
    * @param dict: A dictionary of words dict
    */
    map<string, vector<int>> wordMap;   //the vector<int> stores the index of the strings in dict.
    vector<string> words; // e.g., {"Jason Zhang", James Yu", ...}
    Typeahead(unordered_set<string> dict) {
        int index = ;
        for (auto str : dict) {
            words.push_back(str); 
            //split the string into subWords
            int strSize = str.size();
            for (int i = ; i < strSize; ++i) {
                for (int j = i; j < strSize; ++j) {
                    string subWord = str.substr(i, j - i + );
                    if (wordMap.find(subWord) == wordMap.end()) {
                        wordMap[subWord] = vector<int>(, index);   //generate {index}
                    } else {
                        //remove duplicate: make sure that "Tree" will not enter into the vec twice as it has two 'e'.
                        int vecSize = wordMap[subWord].size();
                        if (wordMap[subWord][vecSize - ] != index) {
                            wordMap[subWord].push_back(index);
                        }
                    }
                }
            }
            index++;
        }
    }

    /*
     * @param str: a string
     * @return: a list of words
     */
    vector<string> search(string &str) {
        vector<string> result;

        if (wordMap.find(str) == wordMap.end()) {
            return result;
        } else {
            for (auto i : wordMap[str]) {
                result.push_back(words[i]);
            }
        }      
        return result;
    }
};
           

如果這題的search是輸入單個first name或last name，則可以簡化用stringstream或split()函數來做。代碼如下：

Typeahead(unordered_set<string> dict) {
        int index = ;
        for (auto str : dict) {
            words.push_back(str); 
            //split the string into words
            stringstream ss(str);
            string buf; //stores the first name or last name like "Jason", "Zhang", etc
            while(ss >> buf) {
                if (wordMap.find(buf) == wordMap.end()) {
                    wordMap[buf] = vector<int>(, index);   //generate {index}
                } else {
                    wordMap[buf].push_back(index);
                }
            }

            index++;
        }
    }
           

另外，這題不知道能不能用Trie做。下次再想想。