Leetcode 212. Word Search II

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数组作为标记数组。
知道了如果搜索一个单词，那么遍历words进行搜索就能得到答案。
题目有一个test case是["a", "a"] 和 [['a']]，返回结果只能是["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树优化版本

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;
}