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

Question

我有一个输入字符串，比如"fairy"，我需要得到可以从中组成的英文单词。这是一个例子：

5: Fairy
4: Fray, Airy, Fair, Fiar
3: Fay, fry, arf, ary, far, etc.

我有 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 个字母的单词.

如何找到更短的单词？我猜它也与排列有关，但我不确定如何实现它。

Answer 1

在算法上，您可以使用类似计数器的东西来生成单词的所有子集，然后找到所有排列：

例如：

00000 ---> null
00001 ---> y
00010 ---> r
00011 ---> ry
00100 ---> i
00101 ---> iy
...
11110 ---> Fair
11111 ---> Fairy

注意：现在，对每个单词执行排列函数以生成字符的其他顺序。 permutation.

见这里

为了实现计数器，使用布尔数组之类的东西，并更改最低位，并在需要时更新其他位。在每个级别中，选择那些在您的布尔数组中索引为真的“字符”。

Answer 2

好吧，你要问自己一个问题。你能重复使用字母吗？例如，如果给你单词 friend，fee 合法吗？ Friend 有 1 个 e 而 fee 有 2 个。这是一个重要但次要的细节。

算法 1：蛮力

您可以遍历整个可能的单词列表并编写一个方法“这个单词是否仅由另一个单词中的字母组成”？如果是，请将其添加到您的最终列表中。

根据您对第一个问题的回答，该算法略有变化，但并不难写。

算法 2：递归方法

创建方法 addWords()。

/**
 * letters is the list of letters you're allowed to use
 * word may not be empty
 */
void addWords(string letters, string word) {
    size_t length = word.length();

    for (int index = 0; index < length; ++index) {
         string newWord = word + letters[index];
         string remainingLetters = letters.substr(0, index) + letters(index + 1);
         // if newword is in your dictionary, add it to the output
         ...
         addWords(remainingLetters, newWord);
    }
}

让我们看看如何使用 addWords("fairy", "") --

第一个循环：将f添加到空字符串中并检查f是否是一个单词。然后使用 addWords("airy", f") 进行递归。我们稍后会介绍递归。

第二个循环：将a添加到空字符串中并检查a是否是一个单词。是的，所以我们将它添加到输出中并使用 addWords("firy", "a").

进行递归

重复检查每个单字母单词（总共 5 次）。

现在，让我们看一下一级递归 -- addWords("airy", "f")。现在，我们将按 fa、fi 等顺序尝试。然后我们将再次递归，如 addWords("iry", "fa") (etc).

从递归第二个循环开始，我们将尝试以 a 而不是 f 开头的单词。所以我们最终会测试 af、ai 等

如果您对第一个问题的回答是“不，我们不重复使用字母”，则此方法有效。如果答案是肯定的，则此方法无效。

Answer 3

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

#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

Answer 4

Trie 可能是存储单词的合适结构。

我还建议使用排序后的字谜作为“键”，而不是直接使用单词：

class Node
{
public:
    std::map<char, Node> children; // Might be an array<std::unique_ptr<Node>, 26>

    std::set<std::string> data; // List of word valid with anagram
    // Traditionally, Trie would use instead ` bool endOfWord = false;`

    Node() = default;

    const Node* get(char c) const
    {
        auto it = children.find(c);

        if (it == children.end()) {
            return nullptr;   
        }
        return &it->second;
    }
};

class Trie
{
    Node root;
public:
 
    void add(const std::string& word)
    {
        std::string sorted = word;
        std::sort(sorted.begin(), sorted.end());
        Node* node = &root;
        for (const char c : sorted) {
            node = &node->children[c];
        }
        node->data.insert(word);
    }
// ...
};

然后打印所有你可能会做的字谜：

void print_valid_words(std::string letters) const
{
    std::sort(letters.begin(), letters.end());
    print_valid_words(&root, letters);
}
    
private:

void print_valid_words(const Node* current, std::string_view letters) const
{
    if (current == nullptr) return;

    for (auto word : current->data) {
        std::cout << word << std::endl;   
    }
    for (std::size_t i = 0; i < letters.size(); ++i)
    {
        if (i == 0 || letters[i] != letters[i - 1]) {
            print_valid_words(current->get(letters[i]), letters.substr(i + 1));
        }
    }
}

Demo

Answer 5

您可以检查每个排列的每个前缀（或后缀，只需保持一致）。这将多次考虑某些子字符串，但这是一个简单的更改。

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

// Finds every permutation (non-duplicate arrangement of letters)
std::sort(letters.begin(), letters.end());
do {
    std::string_view view = letters;
    for (auto i = 1; i < view.size(); ++i) {
        auto prefix = view.substr(0, i);
        // check if prefix is dictionary word
        permutations.insert(prefix);
    }
} while (std::next_permutation(letters.begin(), letters.end()));

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

How to get all dictionary words from a list of letters?

c++

permutation