212. Word Search II

Problem:

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"].

Analysis:

6/6/3028 update:
这道题的思想很简答，但是写成bug free各种情况都考虑到很难。这一遍保存word考虑到了，去重没想到。
--------------------------------------------------------------------------------------------------------------------------------------------
3/6/0218 update:
The problem is how to validate the word found is in words. We use trie tree to achieve it. Then the approach is self explanatory.

Solution:
There are several points that make this implementation very smart.

1. word end in trie node store word directly, so that there is no need to keep track of char traveled. 
2. when found a word, assign it to null removes duplicate.

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>();
        if (board == null || board[0].length == 0)
            return res;
        TrieNode root = new TrieNode();
        int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        buildTrieTree(words, root);
        for (int i = 0; i < board.length; i++) 
            for (int j = 0; j < board[0].length; j++) {
                search(res, board, i, j, root, dirs);
            }

        return res;
    }

    private void search(List<String> res, char[][] board, int x, int y, TrieNode root, int[][] dirs) {
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) {
            return;
        }
        char c  = board[x][y];
        if (c == '#' || root.children[c - 'a'] == null ) return;
        TrieNode curNode = root.children[c - 'a'];
        if (curNode.word != null) {
            res.add(curNode.word);
            // remove dup
            curNode.word = null;
        }

        board[x][y] = '#';
        for (int[] dir: dirs) {
            int newx = x + dir[0];
            int newy = y + dir[1];
            search(res, board, newx, newy, curNode, dirs);
        }
        board[x][y] = c;
    }

    private void buildTrieTree(String[] words, TrieNode root) {
        for (String word: words) {
            TrieNode node = root;
            for (char c: word.toCharArray()) {
                if (node.children[c - 'a'] == null) {
                    node.children[c - 'a'] = new TrieNode();
                }
                node = node.children[c - 'a'];
            }
            node.word = word;
        }
    }

    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word;
    }
}