如何从多字符数组各选1字符排列组合匹配指定单词词典

前置预处理（提升性能） #

• 先把给定的listWords词典转成HashSet<string>类型，后续单词查询时间复杂度为O(1)，远高于数组遍历查询的效率
• 统计词典中所有单词的长度区间：本次给出的词典单词最短长度为2、最长为6，后续生成拼接串时仅处理长度在2~6区间的结果，长度为1或者超过6的直接跳过，减少无效计算
• 可选优化：可以给词典建立前缀树（Trie），后续生成拼接串的过程中可以实时剪枝，如果当前拼接的前缀不在前缀树中，直接终止当前路径的后续拼接，进一步减少运算量

核心遍历逻辑（全覆盖无遗漏） #

我们需要覆盖所有长度≥2的字符数组排列序列，按以下步骤执行：

1. 遍历所有可能的数组选取长度k，k的取值范围是2 ≤ k ≤ min(7, 词典最长单词长度)，本次场景下k从2取到6即可
2. 对每个k值，生成7个字符数组中选k个的所有有序排列（因为数组顺序不同，拼接出来的单词完全不同，比如charArr1+charArr2和charArr2+charArr1是两种完全独立的场景）
3. 对每一组生成的数组排列序列，做笛卡尔积遍历：每个数组仅选取1个字符，按照排列的顺序拼接成完整字符串
4. 把拼接好的字符串放到预处理好的HashSet中查询，如果存在就存入saveWords数组，可对saveWords做去重处理，避免同一个单词被不同排列匹配到导致重复存储

约束满足验证 #

• 符合约束1：所有排列序列中每个字符数组仅出现1次，最多选1个字符，不会出现同一个数组内多个字符拼接的无效情况
• 符合约束2：遍历了所有k≥2的数组排列，所有可能的合法拼接场景都会被覆盖，不会遗漏

比如示例中的sehi，对应的数组排列是charArr1→charArr4→charArr6→charArr7，分别选s、e、h、i拼接而成，匹配词典后会被正常存入结果数组。

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