蛮力法可以解决 O(n!) 的问题,基本上计算所有排列并在字典中检查结果。我正在寻找提高复杂性的方法。我可以考虑从字典中构建一棵树,但仍然检查所有字母排列是 O(n!)。有没有更好的方法来解决这个问题?
字母可以重复。
该函数的 api 如下所示:
List<String> findValidWords(Dict dict, char letters[])
最佳答案
假设 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是单词中的最大字符总数
关于algorithm - 给定一个字典和一个字母列表,找出所有可以用这些字母组成的有效单词,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25298200/