Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,
Given words =["oath","pea","eat","rain"]and board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return ["eat","oath"]

If the current candidate does not exist in all words' prefix, you could stop backtracking immediately. What kind of data structure could answer such query efficiently? Does a hash table work? Why or why not? How about a Trie?

Solution: 把words放到trie。每搜到一个word，把node.hasWord设为false，以免重复

    int[] dx = {1, 0, -1, 0};
    int[] dy = {0, 1, 0, -1};
    TrieNode root;
    public List<String> findWords(char[][] board, String[] words) {
        List<String> ans = new ArrayList<>();
        root = new TrieNode();
        for (String word : words) {
            insert(word);
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                search(root, board, i, j, ans, new StringBuilder());
                if (ans.size() == words.length) {
                    return ans;
                }
            }
        }
        return ans;
    }
    private void search(TrieNode cur, char[][] board, int x, int y, List<String> ans, StringBuilder path) {
        if (cur.hasWord) {
            ans.add(path.toString());
            cur.hasWord = false;
            return;
        }
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] == '.') {
            return;
        }
        cur = cur.hashmap.get(board[x][y]);
        if (cur != null) {
            path.append(board[x][y]);
            char temp = board[x][y];
            board[x][y] = '.';
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                //不可把边界条件的判断放在这，eg: ["a"], ["a"]

                search(cur, board, nx, ny, ans, path);

            }
            board[x][y] = temp;
            path.deleteCharAt(path.length() - 1);
        }
    } 

    public void insert(String word) {
        TrieNode cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (!cur.hashmap.containsKey(c)) {
                cur.hashmap.put(c, new TrieNode());
            }
            cur = cur.hashmap.get(c);
        }
        cur.hasWord = true;
    }

    class TrieNode {
        boolean hasWord;
        Map<Character, TrieNode> hashmap;
        public TrieNode() {
            hashmap = new HashMap<>();
            hasWord = false;
        }
    }