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.

Example:

Input:
words = ["oath","pea","eat","rain"] and board =
[ 
 ['o','a','a','n'],
 ['e','t','a','e'],
 ['i','h','k','r'],
 ['i','f','l','v']
]

Output: ["eat","oath"]

Note:
You may assume that all inputs are consist of lowercase letters a-z.

Thoughts

1. How do we instantly know the current character is invalid? -> hashmap?

2. How do we instantly know what's the next valid character? -> LinkedList

3. But the next character can be chosen from a list of characters. -> "Multi-LinkedList?"

4. Combing them,Trieis the natural choice. Notice that:

   1. No need to store character at TrieNode: c.next[i] != nullis enough.

   2. No need to use O(n^2) extra space visited[m][n]

   3. No need to use StringBuilder. Storing worditself at leaf node is enough

   4. No need to use Hashsetto de-duplicate. Set "cur.word = null" each time when found a character during DFS

5. Optimization:

   1. w.toCharArray() -> w.charAt(i)

   2. visited[m][n] -> board[i][j] = '#'

   3. checking index validity before calling dfs

   4. [c - ''a'] to i

6. Time Complexity

   1. O( l * wl) - Build the Tree

   2. O(min(m * n, wl) * l): worse case cenario. However, if words starting with the same characters and path sharing the cells, Trie can check multiple words when DFS from a certain cell, rather than check only one word when DFS from a certain cell like the naive way - Search

7. Space Complexity:

   1. O(l * wl) = max(O(wl), O(l * wl)) where:

      1. O(wl) recursive call

      2. O(l * wl) In the worst case when all words start with different characters, the trie has l * wl nodes. Also, since each word is stored in a leaf node, all the leaf nodes require l * wl memory (can be augmented by only store a boolean, but need to further discuss how to add found results in res), but the number of nodes stored in the tree is still l * wl;

Code:

class Solution {
    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;
    }
    private void dfs(char[][] board, int i, int j, TrieNode cur, List<String> res){
        char c = board[i][j];
        if(c == '#' || cur.next[c - 'a'] == null) return;
        cur = cur.next[c-'a'];
        if(cur.word != null){
            res.add(cur.word);
            cur.word = null; // de-duplicate
        }
        board[i][j] = '#'; // visited
        if (i > 0) dfs(board, i - 1, j, cur, res);
        if (j > 0) dfs(board, i, j - 1, cur, res);
        if (i + 1< board.length) dfs(board, i + 1, j , cur, res);
        if (j + 1< board[0].length) dfs(board, i, j + 1, cur, res);
        board[i][j] = c;

    }

    private TrieNode buildTrie(String [] words){
        TrieNode root = new TrieNode();
        for(String word: words){
            TrieNode cur = root;
            for (char c: word.toCharArray()){
                if(cur.next[c - 'a']== null) cur.next[c - 'a'] = new TrieNode();
                cur = cur.next[c - 'a'];
            }
            cur.word = word;
        }     

        return root;
    }

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

Reference to this post