如何从字母列表中获取词典中的所有单词?

2022-04-03 00:00:00 permutation c++

我有一个输入字符串,如"fairy",我需要从它获取可以组成的英语单词。下面是一个例子:

5:仙女
4:FRAY、AIRY、FIRE、FIAR
3:Fay、Fry、Arf、ary、Far等

我有std::unordered_set<std::string>词典单词,所以我可以很容易地迭代它。我以前创建过排列,如下所示:

std::unordered_set<std::string> permutations;

// Finds every permutation (non-duplicate arrangement of letters)
std::sort(letters.begin(), letters.end());
do {
    // Check if the word is a valid dictionary word first
    permutations.insert(letters);
} while (std::next_permutation(letters.begin(), letters.end()));

这对于长度为5非常合适。我可以检查每个letters是否匹配,最后得到"fairy",这是从这些字母中可以找到的唯一5个字母的单词。

我如何才能找到较小长度的单词?我猜它也与排列有关,但我不确定如何实现它。


解决方案

您可以保留一个辅助数据结构,并添加一个特殊符号来标记行尾:

#include <algorithm>
#include <string>
#include <set>
#include <list>
#include <iostream>
 
int main()
{
    std::list<int> l = {-1, 0 ,1, 2, 3, 4};
    std::string s = "fairy";
    std::set<std::string> words;
    do {
        std::string temp = "";
        for (auto e : l)
            if (e != -1) temp += s[e];
            else break;
        words.insert(temp);
    } while(std::next_permutation(l.begin(), l.end()));
}

这里的特殊符号是-1

相关文章