[LeetCode] Problem 212 - Word Search II

Posted on | In ,

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.

Example

Input: 

1
2
3
4
5
6
board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

words = [“oath”,”pea”,”eat”,”rain”]

Output: [“eat”,”oath”]

Note

  1. All inputs are consist of lowercase letters a-z.
  2. The values of words are distinct.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
public class TrieNode {
    private String word;
    private Map<Character, TrieNode> children = new HashMap<>();
}

public class TrieTree {
    private TrieNode root;

    public TrieTree(TrieNode root) {
        this.root = root;
    }

    public void insert(String word) {
        TrieNode node = root;

        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            node.children.putIfAbsent(ch, new TrieNode());
            node = node.children.get(ch);
        }

        node.word = word;
    }
}

public List<String> findWords(char[][] board, String[] words) {
    List<String> result = new ArrayList<>();
    TrieTree trieTree = new TrieTree(new TrieNode());

    for (String word : words)
        trieTree.insert(word);

    int n = board.length;
    int m = board[0].length;
    boolean[][] visit = new boolean[n][m];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++)
            dfs(result, board, visit, trieTree.root, n, m, i, j);
    }

    return result;
}

private void dfs(List<String> result, char[][] board, boolean[][] visit, TrieNode trieNode, int n, int m, int x, int y) {
    char ch = board[x][y];

    if (!trieNode.children.containsKey(ch) || visit[x][y])
        return;

    TrieNode child = trieNode.children.get(ch);
    String word = child.word;

    if (word != null && !result.contains(word))
        result.add(word);

    visit[x][y] = true;

    if (x + 1 < n)
        dfs(result, board, visit, child, n, m, x + 1, y);
    if (x - 1 >= 0)
        dfs(result, board, visit, child, n, m, x - 1, y);
    if (y + 1 < m)
        dfs(result, board, visit, child, n, m, x, y + 1);
    if (y - 1 >= 0)
        dfs(result, board, visit, child, n, m, x, y - 1);

    visit[x][y] = false;
}