如何使用C++从给定字母序列中提取所有可构成的合法字典单词

方法1：基于现有排列逻辑的扩展 #

你当前的实现是生成原字符串全长度的全排列，要获取更短的可组成单词，只需要增加「选取固定长度字母子集」的步骤即可，整体逻辑和你现有代码完全兼容：

• 先确定你需要匹配的单词长度范围，比如从3到原字符串长度
• 对每个目标长度k，生成原字符串所有长度为k的无重复字母子集
• 对每个子集执行你现有的全排列逻辑，生成所有无重复排列
• 逐个查询排列是否存在于字典集合中，存在的即为符合要求的单词

代码示例：

#include <vector>
#include <string>
#include <algorithm>
#include <unordered_set>

std::unordered_set<std::string> getValidWords(std::string letters, const std::unordered_set<std::string>& dict, int minLen = 3) {
    std::unordered_set<std::string> res;
    int n = letters.size();
    std::sort(letters.begin(), letters.end()); // 排序方便后续去重和排列生成

    // 遍历所有目标单词长度
    for (int k = minLen; k <= n; ++k) {
        // 生成选择掩码，标记要选中的k个字母位置
        std::vector<bool> mask(n, false);
        std::fill(mask.end() - k, mask.end(), true);
        do {
            // 取出选中的字母组成子集
            std::string subset;
            for (int i = 0; i < n; ++i) {
                if (mask[i]) subset += letters[i];
            }
            // 对子集做全排列，查询字典
            std::sort(subset.begin(), subset.end());
            do {
                if (dict.count(subset)) {
                    res.insert(subset);
                }
            } while (std::next_permutation(subset.begin(), subset.end()));
        } while (std::next_permutation(mask.begin(), mask.end()));
    }
    return res;
}

该方法的优点是理解成本低，和你现有逻辑无缝衔接；缺点是如果原字符串长度超过8，排列组合数量会指数级上升，性能下降明显。

方法2：更高效的字符频率匹配法 #

如果你的字典规模不大（常用英文单词仅10万量级），更推荐直接遍历字典校验，不需要生成任何排列，性能高很多：

• 先统计原字符串每个字符的出现次数，存为计数数组
• 遍历字典中的每个单词：
  1. 先判断单词长度是否在你需要的范围内，不符合直接跳过
  2. 统计当前单词的字符出现次数
  3. 校验该单词的所有字符的计数都不超过原字符串的对应字符计数，符合的即为有效单词

代码示例：

#include <array>
#include <string>
#include <unordered_set>
#include <cctype>

std::unordered_set<std::string> getValidWords(std::string letters, const std::unordered_set<std::string>& dict, int minLen = 3) {
    std::unordered_set<std::string> res;
    int n = letters.size();
    // 统计原字符串字符计数，默认兼容大小写，可根据需求调整
    std::array<int, 26> originCnt = {0};
    for (char c : letters) {
        originCnt[tolower(c) - 'a']++;
    }

    for (const std::string& word : dict) {
        int len = word.size();
        if (len < minLen || len > n) continue;
        std::array<int, 26> wordCnt = {0};
        bool valid = true;
        for (char c : word) {
            int idx = tolower(c) - 'a';
            wordCnt[idx]++;
            // 只要有一个字符超过原字符串的存量，直接标记无效跳出
            if (wordCnt[idx] > originCnt[idx]) {
                valid = false;
                break;
            }
        }
        if (valid) {
            res.insert(word);
        }
    }
    return res;
}

该方法的性能不受原字符串长度影响，就算原字符串长度为10也不会有性能问题，也不需要额外处理排列去重的逻辑。

注意事项 #

建议统一将字母和字典单词转为全小写/全大写再做匹配，避免大小写不一致导致匹配失败。

内容的提问来源于stack exchange，提问作者CodingScienc