/*     *212. Word Search II      *2016-6-11 by Mingyang     *这真的是我见过最好玩的题目了，在已经有了Trie的基础上，我们再继续往下看     *直接利用这个工具，每次都传进去，这样后面就可以不断的使用这个工具     *然后首先的思路就是把Trie填满需要的东西     *然后就是对每一个位置进行dfs。记住要使用visit map来进行定位     */    public List
     
       findWords(char[][] board, String[] words) {        HashSet
      
        list = new HashSet();        Tries trie = new Tries();        for (String word : words)            trie.insert(word);        boolean[][] visited = new boolean[board.length][board[0].length];        for (int i = 0; i < board.length; i++)            for (int j = 0; j < board[0].length; j++)                dfss(list, board, visited, "", i, j, trie);        return new ArrayList(list);    }    public void dfss(Set
       
         list, char[][] board, boolean[][] visited,            String str, int x, int y, Tries trie) {        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length)            return;        if (visited[x][y])            return;        str += board[x][y];        if (!trie.startsWith(str))            return;        if (trie.search(str))            list.add(str);        visited[x][y] = true;        dfss(list, board, visited, str, x - 1, y, trie);        dfss(list, board, visited, str, x + 1, y, trie);        dfss(list, board, visited, str, x, y - 1, trie);        dfss(list, board, visited, str, x, y + 1, trie);        visited[x][y] = false;    }}class Tries {    public TrieNode root;    public Tries() {        root = new TrieNode();        root.isEnd = true;    }    public void insert(String word) {        if (word == null || word.length() == 0)            return;        TrieNode node = root;        char[] letters = word.toCharArray();        for (int i = 0; i < word.length(); i++) {            int pos = letters[i] - 'a';            if (node.son[pos] == null) {                node.son[pos] = new TrieNode();                node.son[pos].val = letters[i];            }            node = node.son[pos];        }        node.isEnd = true;    }    // Returns if the word is in the trie.    public boolean search(String word) {        if (word == null || word.length() == 0) {            return false;        }        TrieNode node = root;        char[] letters = word.toCharArray();        for (int i = 0; i < word.length(); i++) {            int pos = letters[i] - 'a';            if (node.son[pos] != null) {                node = node.son[pos];            } else {                return false;            }        }        return node.isEnd;    }    // Returns if there is any word in the trie    // that starts with the given prefix.    public boolean startsWith(String prefix) {        if (prefix == null || prefix.length() == 0) {            return false;        }        TrieNode node = root;        char[] letters = prefix.toCharArray();        for (int i = 0; i < prefix.length(); i++) {            int pos = letters[i] - 'a';            if (node.son[pos] != null) {                node = node.son[pos];            } else {                return false;            }        }        return true;    }}class TrieNode {    // Initialize your data structure here.    TrieNode[] son;// 所有的儿子节点    boolean isEnd;// 是不是最后一个节点    char val;// 节点的值    TrieNode() {        this.son = new TrieNode[26];        this.isEnd = false;    }}