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

思路：
首先想到的是如何在一個board中搜索一個單詞失晴。以board中每個字符嘗試作為單詞首部涂屁，進行深度搜索灰伟。由于board每個字符拆又，在一個單詞中最多允許用一次帖族，因此需要一個boolean數(shù)組作為標記數(shù)組挡爵。
知道了如果搜索一個單詞，那么遍歷words進行搜索就能得到答案捻激。
題目有一個test case是["a", "a"] 和 [['a']]前计，返回結(jié)果只能是["a"]，因此為了滿足此case男杈，需要事先對words進行去重。

public List<String> findWords(char[][] board, String[] words) {
    Set<String> set = new HashSet<>();
    for (String word : words) {
        set.add(word);
    }

    List<String> res = new ArrayList<>();
    for (String word : set) {
        if (findWord(board, word)) {
            res.add(word);
        }
    }

    return res;
}

private boolean findWord(char[][] board, String word) {
    int m = board.length, n = board[0].length;
    boolean[][] used = new boolean[m][n];

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (findHelper(board, used, word, 0, i, j)) {
                return true;
            }
        }
    }

    return false;
}

private boolean findHelper(char[][] board, boolean[][] used, String word, int pos, int x, int y) {
    if (pos == word.length()) {
        return true;
    }

    int m = board.length, n = board[0].length;
    if (x < 0 || x >= m || y < 0 || y >= n) {
        return false;
    }

    if (board[x][y] != word.charAt(pos) || used[x][y]) {
        return false;
    }

    used[x][y] = true;
    boolean res = findHelper(board, used, word, pos + 1, x + 1, y) ||
            findHelper(board, used, word, pos + 1, x - 1, y) ||
            findHelper(board, used, word, pos + 1, x, y + 1) ||
            findHelper(board, used, word, pos + 1, x, y - 1);
    used[x][y] = false;
    return res;
}

Trie樹優(yōu)化版本

public List<String> findWords(char[][] board, String[] words) {
List<String> res = new ArrayList<>();
TrieNode root = buildTrie(words);
for (int i = 0; i < board.length; i++) {
    for (int j = 0; j < board[0].length; j++) {
        dfs (board, i, j, root, res);
    }
}
return res;
}

public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
char c = board[i][j];
if (c == '#' || p.next[c - 'a'] == null) return;
p = p.next[c - 'a'];
if (p.word != null) {   // found one
    res.add(p.word);
    p.word = null;     // de-duplicate
}

board[i][j] = '#';
if (i > 0) dfs(board, i - 1, j ,p, res); 
if (j > 0) dfs(board, i, j - 1, p, res);
if (i < board.length - 1) dfs(board, i + 1, j, p, res); 
if (j < board[0].length - 1) dfs(board, i, j + 1, p, res); 
board[i][j] = c;
}

public TrieNode buildTrie(String[] words) {
TrieNode root = new TrieNode();
for (String w : words) {
    TrieNode p = root;
    for (char c : w.toCharArray()) {
        int i = c - 'a';
        if (p.next[i] == null) p.next[i] = new TrieNode();
        p = p.next[i];
   }
   p.word = w;
}
return root;
}

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