DFS+Trie—— DrawSomething辅助
最近 DrawSomething （你画我猜）挺火的，于是就写了个辅助工具。
DrawSomething的游戏规则是：
用N个候选字母构造一个M长度的单词
输入: 候选字符集，单词长度
输出: 所有符合的单词
算法思路：
使用单词表构造Trie树，在搜索的时候将尝试循环尝试候选集里面每一个字符，如果存在有效路径，则从候选集里删除此字符，进入到下一层的搜索。一直到层数达到目标数量时，检查此路径组成的单词是否是有效单词（在Trie树构造的时候已经在Node上标记了 ），如果有效则加入结果中。
时间复杂度：
- 构造 Trie树： O(N) N为单词表总字符数
- 搜索: O(M!/(M-N)!) M 为候选集大小、 N为目标单词长度。 这个其实就是枚举的时间复杂度，但是因为实在Trie树上进行的枚举搜索，所以在无效的路径情况下会立即终止，实际上是进行了非常多的搜索剪枝，实际运行时间远小于理论上界。
最大使用40万单词的词库测试 ，但是还是秒出，速度挺快的。
package org.huohua.drawsomething;
import java.util.ArrayList;
import java.util.*;
class TrieNode {
TrieNode[] children;
boolean end;
int maxdeep;
static Set<String> Result = new HashSet<String>();
TrieNode() {
children = new TrieNode[26];
end = false;
maxdeep = 0;
}
private int ord(char c) {
return c - 'a';
}
int Insert(String word, int index) {
if (index == word.length()) {
end = true;
return 0;
}
int sub = ord(word.charAt(index));
if (children[sub] == null) {
children[sub] = new TrieNode();
}
int deep = children[sub].Insert(word, index + 1);
if (deep + 1 > maxdeep) maxdeep = deep + 1;
return deep + 1;
}
// Drawsomething查找， 从当前节点出发，只允许使用chars集合中的字母，找到剩余num长度的单词。 cur为前面的字符部分
boolean FindDrawSomething(String chars, int num, String cur) {
if (maxdeep < num)
return false;
// 已经到最大长度
if (num == 0) {
// 如果此节点是一个单词的结束， 则搜索成功
if (end) {
Result.add(cur);
return true;
}
return false;
}
boolean found = false;
// 对于每一个剩余的可选字符，尝试是否有有效的Trie路径
for (int i = 0; i < chars.length(); ++i) {
int sub = ord(chars.charAt(i));
if (sub > 25 || sub < 0)
continue;
if (children[sub] == null)
continue;
// 将当前选中的字符从 chars 中剔除，进行下一层搜索
String nextchars = chars.substring(0, i) + chars.substring(i + 1);
boolean ret = children[sub].FindDrawSomething(nextchars, num - 1, cur + chars.charAt(i));
if (ret)
found = true;
}
return found;
}
}
public class TrieTree {
TrieNode root;
public TrieTree(ArrayList<String> words) {
root = new TrieNode();
for (String word : words) {
Insert(word.toLowerCase());
}
}
void Insert(String word) {
root.Insert(word, 0);
}
boolean FindDrawSomething(String chars, int num) {
if (chars.length() < num)
return false;
TrieNode.Result.clear();
return root.FindDrawSomething(chars.toLowerCase(), num, "");
}
}
测试结果：
Back