@@ -0,0 +1,2089 @@
+import java.util.*;%0A%0Apublic class WordSearchII %7B%0A    private TrieNode root = new TrieNode('0');%0A%0A    static class TrieNode %7B%0A        char letter;%0A        Map%3CCharacter, TrieNode%3E children = new HashMap%3CCharacter, TrieNode%3E();%0A        boolean isEnd;%0A%0A        public TrieNode(char letter) %7B this.letter = letter; %7D%0A    %7D%0A%0A    public void buildTrie(String word) %7B%0A        TrieNode curr = root;%0A        for (char c : word.toCharArray()) %7B%0A            if (curr.children.containsKey(c)) %7B%0A                curr = curr.children.get(c);%0A            %7D else %7B%0A                TrieNode node = new TrieNode(c);%0A                curr.children.put(c, node);%0A                curr = node;%0A            %7D%0A        %7D%0A        curr.isEnd = true;%0A    %7D%0A%0A    public List%3CString%3E wordSearchII(char%5B%5D%5B%5D board, List%3CString%3E words) %7B%0A        if (board == null %7C%7C board.length == 0 %7C%7C board%5B0%5D.length == 0) return null;%0A        for (String word : words) buildTrie(word);%0A        LinkedHashSet%3CString%3E ret = new LinkedHashSet%3CString%3E();%0A        boolean%5B%5D%5B%5D visited = new boolean%5Bboard.length%5D%5Bboard%5B0%5D.length%5D;%0A        for (int i = 0; i %3C board.length; i++) %7B%0A            for (int j = 0; j %3C board%5B0%5D.length; j++) %7B%0A                helper(board, i, j, root, visited, %22%22, ret);%0A            %7D%0A        %7D%0A%0A        List%3CString%3E result = new ArrayList%3CString%3E();%0A        for (String word : ret) result.add(word);%0A        return result;%0A    %7D%0A%0A    public void helper(char%5B%5D%5B%5D board, int i, int j, TrieNode node, boolean%5B%5D%5B%5D visited, String temp, LinkedHashSet%3CString%3E res) %7B%0A        if (i %3C 0 %7C%7C i %3E= board.length %7C%7C j %3C 0 %7C%7C j %3E= board%5B0%5D.length) return;%0A        if (root == null %7C%7C !root.children.containsKey(board%5Bi%5D%5Bj%5D) %7C%7C visited%5Bi%5D%5Bj%5D) return;%0A%0A        temp += board%5Bi%5D%5Bj%5D;%0A        if (root.children.get(board%5Bi%5D%5Bj%5D).isEnd) res.add(temp);%0A%0A        visited%5Bi%5D%5Bj%5D = true;%0A        int%5B%5D x = %7B0, 0, -1, 1%7D;%0A        int%5B%5D y = %7B1, -1, 0, 0%7D;%0A        for (int k = 0; k %3C 4; k++) %7B%0A            helper(board, i + x%5Bk%5D, j + y%5Bk%5D, node.children.get(board%5Bi%5D%5Bj%5D), visited, temp, res);%0A        %7D%0A        visited%5Bi%5D%5Bj%5D = false;%0A    %7D%0A%7D%0A

Implement using Trie