最近 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, "");
    }

}

测试结果：

view on github