Interview Question - combine wor

Question:
第一题是给一个string，一个dict，要求返回dict中的string，其可以由string中的char组成（每个char最多用一次），最后返回一个list。

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=202089&highlight=snapchat

My code:

// combine words using string
    public List<String> wordSearch(String s, String[] wordDict) {
        buildTrie(wordDict);
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++) {
            char curr = s.charAt(i);
            if (!map.containsKey(curr)) {
                map.put(curr, 1);
            }
        }
        List<String> ret = new ArrayList<String>();
        helper(root, map.keySet().size(), map, ret);
        return ret;
    }
    
    private void helper(TrieNode root, int level, Map<Character, Integer> map, List<String> ret) {
        if (level == 0) {
            if (root.isWord) {
                ret.add(root.s);
            }
            return;
        }
        if (root.isWord) {
            ret.add(root.s);
        }
        
        for (int i = 0; i < 26; i++) {
            if (root.next[i] != null) {
                char val = (char) (i + 'a');
                if (!map.containsKey(val) || map.get(val) <= 0) {
                    continue;
                }
                else {
                    map.put(val, 0);
                    helper(root.next[i], level - 1, map, ret);
                    map.put(val, 1);
                }
            }
        }
    }

TrieNode root = new Trie('r');
private void buildTrie(String[] arr) {
    for (String s : arr) {
        insert(s, 0, root);
    }
}

private void insert(String s, int index, TrieNode root) {
    if (index >= s.length()) {
        root.isWord = true;
        root.s = s;
    }
    else {
        char curr = s.charAt(index);
        if (root.next[curr - 'a'] == null) {
            root.next[curr - 'a'] = new TrieNode(curr);
        }
        insert(s, index + 1, root.next[curr - 'a']);
    }
}

class TrieNode {
    TrieNode[] next = new TrieNode[26];
    char val;
    boolean isWord;
    String s;
    TrieNode(char val) {
        this.val = val;
    }
}

代码又多个部分拼接而成。将就着看吧。

这一题和 combine words using words 有什么区别？
那一题，首先， char 可以重复，其次，最关键的，是拿一个string去combine 多个 words，Trie 的话，只能 match 一个word，所以不能用。
而这道题目，就是拿不重复的char,去组成word，看看能组成多少个word。所以可以建Trie 来做。

主体思想还是把 pattern 压缩成 char[26] 或者hashmap, 然后来做。

Anyway, Good luck, Richardo! -- 09/27/2016