向量搜索押韵字

Question

在我的程序中，我必须提示用户输入一个单词，并报告所有押韵的单词(通过检查最后3个字母是否相同)。

例如，如果用户输入了单词"time“，我必须返回lime、dime、intime、entered等，形成一个有106,000个单词的向量。

所有106,000个单词都在一个向量vector<string>words中，该向量将包含

time, lime, line, dime, intime, abaca, clilica, dog, ball, regime, sentence, return, which, contain, word, pool, etc....

在所有这些之外，我需要获得与用户输入的单词节奏相同的单词。

如何使用用户输入的字符串创建一个函数来查找所有这些内容？

Answer 1

你说rhyme = the last 3 letters are the same。向量中的10万6千个单词意味着你有足够的内存，所以建议使用下面的方法来换取空间。

unordered_map<string, vector<string>> rhymesMap;
int const rhymesSuffixLength = 3;

void preProcess(vector<string>& words){
    for(auto const& word: words){
        if(word.size() < rhymesSuffixLength)
            continue;
        string suffix = word.substr(word.size() - rhymesSuffixLength);
        rhymesMap[suffix].push_back(word);
    }
}

vector<string> getRhymes(string word){
    if(word.size() < rhymesSuffixLength)
        return {};
    string suffix = word.substr(word.size() - rhymesSuffixLength);
    return rhymesMap[suffix];
}

从vector上搜索押韵太慢了，unordered_map需要查找，而且相当快。