给定一个字典和一个字母列表,找到可以用字母构建的所有有效单词

Question

蛮力方式可以解决O(n!)中的问题,基本上计算所有排列并检查字典中的结果.我正在寻找提高复杂性的方法.我可以考虑从字典中构建一个树,但仍然检查所有字母排列是O(n!).有没有更好的方法来解决这个问题？

信件可以有重复.

该函数的api如下所示:

List<String> findValidWords(Dict dict, char letters[])

Answer 1

假设letters只包含a到z的字母.

使用整数数组计算字符的出现次数letters.

对于字典中的每个单词,检查单词中是否出现超出允许的单词,如果没有,请将该单词添加到 result.

    List<String> findValidWords(List<String> dict, char letters[]){
        int []avail = new int[26];
        for(char c : letters){
            int index = c - 'a';
            avail[index]++;
        }
        List<String> result = new ArrayList();
        for(String word: dict){
            int []count = new int[26];
            boolean ok = true;
            for(char c : word.toCharArray()){
                int index = c - 'a';
                count[index]++;
                if(count[index] > avail[index]){
                    ok = false;
                    break;
                }
            }
            if(ok){
                result.add(word);
            }
        }
        return result;
    }

所以我们可以看到时间复杂度是O(m*k),m是字典中的单词数,k是单词中字符的最大总数

Answer 2

您可以对字典中的每个单词进行排序,使字母与字母表中的单词顺序相同,然后从排序后的单词中构建一个trie.(其中每个节点包含可以用字母组成的所有单词的列表).(字典总字母长度的线性时间)然后,给定一组查询字母,以相同的方式对字母进行排序,并使用从左到右使用字母子集的所有可能方向中的深度优先搜索来继续使用特里.每当您到达包含单词的trie中的节点时,输出这些单词.您探索的每个路径都可以收费至字典中的至少一个单词,因此查找包含您可以制作单词的所有节点的最坏情况复杂度为O(kn),其中n是字典中单词的数量,k是单词中的最大字母数.但是对于某些受限制的查询字母集,每个查询的运行时间应该快得多.