如何从字母列表中获取词典中的所有单词？ [英] How to get all dictionary words from a list of letters?

问题描述

我有一个输入字符串，如"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

这篇关于如何从字母列表中获取词典中的所有单词？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！