@@ -0,0 +1,2279 @@
+package leetcode.map;%0A%0Aimport java.util.ArrayList;%0Aimport java.util.List;%0A%0A/**%0A Given a 2D board and a list of words from the dictionary, find all words in the board.%0A%0A Each word must be constructed from letters of sequentially adjacent cell, where %22adjacent%22 cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.%0A%0A For example,%0A Given words = %5B%22oath%22,%22pea%22,%22eat%22,%22rain%22%5D and board =%0A%0A %5B%0A %5B'o','a','a','n'%5D,%0A %5B'e','t','a','e'%5D,%0A %5B'i','h','k','r'%5D,%0A %5B'i','f','l','v'%5D%0A %5D%0A Return %5B%22eat%22,%22oath%22%5D.%0A */%0Apublic class WordSearchII5 %7B%0A    public List%3CString%3E findWords(char%5B%5D%5B%5D board, String%5B%5D words) %7B%0A       Node root = buildTrie(words);%0A%0A       List%3CString%3E result = new ArrayList%3C%3E();%0A%0A       for (int i=0; i%3Cboard.length; i++) %7B%0A           for (int j=0; j%3Cboard%5B0%5D.length; j++) %7B%0A               find(board, i, j, result, root);%0A           %7D%0A       %7D%0A%0A       return result;%0A    %7D%0A%0A    private void find(char%5B%5D%5B%5D board, int i, int j, List%3CString%3E result, Node root) %7B%0A        if (i%3C0 %7C%7C i%3E= board.length %7C%7C j%3C0 %7C%7C j%3E= board%5B0%5D.length) %7B%0A            return;%0A        %7D%0A%0A        char c = board%5Bi%5D%5Bj%5D;%0A        if (c == '#' %7C%7C root.next%5Bc -'a'%5D == null) %7B%0A            return;%0A        %7D%0A%0A        if (root.next%5Bc -'a'%5D.word != null) %7B%0A            result.add(root.next%5Bc -'a'%5D.word);%0A            root.next%5Bc -'a'%5D.word = null;%0A        %7D%0A%0A        board%5Bi%5D%5Bj%5D = '#';%0A%0A        find(board, i, j-1, result, root.next%5Bc-'a'%5D);%0A        find(board, i, j+1, result, root.next%5Bc-'a'%5D);%0A        find(board, i-1, j, result, root.next%5Bc-'a'%5D);%0A        find(board, i+1, j, result, root.next%5Bc-'a'%5D);%0A        board%5Bi%5D%5Bj%5D = c;%0A    %7D%0A%0A    private Node buildTrie(String%5B%5D words) %7B%0A        Node root = new Node();%0A%0A        for (String word: words) %7B%0A            Node cursor = root;%0A            for (char c: word.toCharArray()) %7B%0A                if (cursor.next%5Bc-'a'%5D == null) %7B%0A                    cursor.next%5Bc-'a'%5D = new Node();%0A                %7D%0A                cursor = cursor.next%5Bc-'a'%5D;%0A            %7D%0A            cursor.word = word;%0A        %7D%0A%0A        return root;%0A    %7D%0A%0A    public class Node %7B%0A        String word = null;%0A        Node%5B%5D next;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        char%5B%5D a = new char%5B26%5D;%0A    %7D%0A%7D%0A

word search ii