时间戳

首页 > 解决方案 > 有没有办法使用有限的字母范围搜索 unordered_set？

c++ - 有没有办法使用有限的字母范围搜索 unordered_set？

问题描述

上下文：我正在用 C++ 编写一个作业，用户输入一个单词或一个句子以逐字解读。我有一个充满英语单词的文本文件，我已将其读入 unordered_set 字符串。然后我检查每个输入单词的排列并尝试在 unordered_set 中找到它。未加扰的单词可能性被打印给用户。

问题：文本文件中有很多单词。该程序无法正常运行，因为遍历所有排列并在 unordered_set 中寻找匹配项需要很长时间。

可能的解决方案：我想限制要搜索的单词范围，因为文本文件已经按字母顺序排列。例如，如果加扰的词是“cit”，那么这个词的一个排列是“itc”。我想在 unordered_set 中以 i 开头的所有单词搜索“itc”。

这是我到目前为止所拥有的。

void unscramble() {

    //issue - too slow, find in range?
    string word;
    string temp;
    ifstream inDictionaryFile("words_alpha.txt");
    unordered_set<string> dictionary;

    //read dictionary file into a unordered_set
    while (getline(inDictionaryFile, temp)) {
        auto result = dictionary.insert(temp + " ");
    }
    cout << "Enter something to unscramble: ";

    //find/print out matches for permuations of scrambled words
    while (cin>>word) {
        do {
            word = word + " ";
            auto result = dictionary.find(word);
            if (result != end(dictionary)) {
                cout << setw(10) << word;
            }
        } while (next_permutation(begin(word), end(word)));
    }


}

标签： c++stringsearch

解决方案

如果您只需要前 3 个字母的排列，您可以使用 unordered_multiset，其键等于规范排列（例如，排序的前 3 个字母）。但我想你的实际问题不应该只用一个数据结构来解决，而是用几个数据结构来解决，一个数据结构用于存储，其他数据结构用于该存储的索引。

推荐阅读