algorithm - 给定一个字典和一个字母列表，找出所有可以用这些字母组成的有效单词

Question

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

字母可以重复。

该函数的 api 如下所示:

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

Answer 1

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

使用一个整数数组来计算一个字符在字母中出现的次数。

对于字典中的每个单词，检查单词中是否有特定字符出现次数超过允许的次数，如果没有，则将此单词添加到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是单词中的最大字符总数