给定字典和字母的列表找到可以以字母构建所有有效字 [英] Given a dictionary and a list of letters find all valid words that can be built with the letters

问题描述

的强制方法可以解决问题，为O（n！），基本计算所有的排列和检查结果的字典中。我在寻找各种方法来提高复杂性。我能想到建立一个树了字典，但还是检查所有字母排列为O（n！）。是否有更好的方法来解决这个问题？

字母可以重复的。

的API函数如下：

 名单，其中，字符串＆GT; findValidWords（字典词典，字符字母[]）
 

解决方案

假设字母只包含从信件到z。

使用一个整型数组来计数字母出现的字符数量。

有关在字典中的每个字，检查是否有允许在出现多字一个特定的字符，如果不加这句话到结果。

 名单，其中，字符串＆GT; findValidWords（名单＆LT;字符串＆GT;快译通，字符字母[]）{
        INT []无济于事=新INT [26];
        对于（字符C：字母）{
            INT指数= C  - 'A';
            果[指数] ++;
        }
        名单＆LT;字符串＆GT;结果=新的ArrayList（）;
        对（串词：字典）{
            INT []数=新INT [26];
            布尔OK = TRUE;
            对于（字符C：word.toCharArray（））{
                INT指数= C  - 'A';
                算上[指数] ++;
                如果（计数[指数]＆GT;利用[指数]）{
                    OK = FALSE;
                    打破;
                }
            }
            如果（OK）{
                result.add（字）;
            }
        }
        返回结果;
    }
 

因此​​，我们可以看到，时间复杂度为 O（M * K）与m是字典中的单词数，k为最大总字符的一个字

The brute force way can solve the problem in O(n!), basically calculating all the permutations and checking the results in a dictionary. I am looking for ways to improve the complexity. I can think of building a tree out of the dictionary but still checking all letters permutations is O(n!). Are there better ways to solve this problem?

Letters can have duplicates.

The api for the function looks like this:

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

解决方案

Assume that letters only contains letters from a to z.

Use an integer array to count the number of occurrence of a character in letters.

For each word in the dictionary, check if there is a specific character in the word that appears more than allowed, if not, add this word into 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;
    }

So we can see that the time complexity is O(m*k) with m is number of word in the dictionary and k is the maximum total of characters in a word

这篇关于给定字典和字母的列表找到可以以字母构建所有有效字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！