Interview Question - get strings by prefix

完了还剩20多分钟就是在线做一道类似浏览器输入keyword搜索给出提示这样的题。自然用trie来做，和leetcode 208差不多，不同的是输入prefix，返回所有单词（dfs或bfs均可）。

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

My code:

// get string using prefix
    private TrieNode root = new TrieNode('r');
    public List<String> prefixString(String prefix, String[] arr) {
        buildTrie(arr);
        TrieNode node = search(prefix, 0, root);
        List<String> ret = new ArrayList<String>();
        if (node == null) {
            return null;
        }
        dfs(node, ret);
        return ret;
    }
    
    private void dfs(TrieNode root, List<String> ret) {
        if (root.isWord) {
            ret.add(root.s);
        }
        for (int i = 0; i < 26; i++) {
            if (root.next[i] != null) {
                dfs(root.next[i], ret);
            }
        }
    }
    
    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']);
        }
    }
    
    private TrieNode search(String s, int index, TrieNode root) {
        if (index >= s.length()) {
            return root;
        }
        char curr = s.charAt(index);
        if (root.next[curr - 'a'] == null) {
            return null;
        }
        return search(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;
    }
}

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