如何从字母列表中获取词典中的所有单词?
我有一个输入字符串,如"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
相关文章