Java: How to implement finding a word from 2D array (word search)?

Question

Given a 2D board and a list of words from the dictionary, I would like to 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"].

And came across the following implementation:

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

And in buildTrie(String[] words), after setting up the trie for a particular word, it does p.word = w;. And in dfs(...), it checks for if (p.word != null).

But how is it that the p.word is null until the very last of the character in a word has been found, then p.word is not null anymore?

p.word is not dependent on any indexes and it is directly related to the object itself, so should be able to be accessed at any point, but I just do not understand how it is null until the very last character of the word has been found.

Thank you

Kaidul Kaidul · Accepted Answer · 2016-11-26T06:08:54

This is a sample trie:

Considering the above trie, during constructing the trie, the word is null by default for every node except in the node where it ends.

For exaple, on inserting buy in the above trie, we scan every characters of word buy and put it per one node. And when we reaches the last character y, we put buy into word variable of that node. That's why you will find every other node's word equal to null except the node where it ends.

Java: How to implement finding a word from 2D array (word search)?

1 Answers