212. Word Search II

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:

Input: 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"]

Example 2:

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

Constraints:

• m == board.length

• n == board[i].length

• 1 <= m, n <= 12

• board[i][j] is a lowercase English letter.

• 1 <= words.length <= 3 * 104

• 1 <= words[i].length <= 10

• words[i] consists of lowercase English letters.

• All the strings of words are unique.

Solution

Tire + DFS

Intuitively, start from every cell and try to build a word in the dictionary. Backtracking (dfs) is the powerful way to exhaust every possible ways. Apparently, we need to do pruning when current character is not in any word.

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. "Mutil-LinkedList"?

Combing them, Trie is the natural choice. Notice that:

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        int m = board.length, n = board[0].length;

        Tire root = buildTire(words);
         for(int i = 0; i < m; i++ ){
            for(int j = 0; j < n; j++){
                dfs(board, i, j, root, result);
            }       
        }
        return result;
    }
    
    
    public void dfs(char[][] board, int i, int j, Tire node, List<String> result){
        int m = board.length, n = board[0].length;
        if(i < 0 || j < 0 || i >= m || j >= n || board[i][j] == ' ') return;
        char c = board[i][j];
        Tire newNode = node.nextNode[c-'a'];
        if(newNode == null) return;
        if(newNode.word != null){
            result.add(newNode.word);
            newNode.word = null;
        }
        board[i][j] = ' ';
        dfs(board, i+1, j, newNode, result);
        dfs(board, i-1, j, newNode, result);
        dfs(board, i, j+1, newNode, result); 
        dfs(board, i, j-1, newNode, result);
        board[i][j] = c;
    }
    
    public Tire buildTire(String[] words){
        Tire root = new Tire();
        for(String word : words){
            Tire p = root;
            for(char c : word.toCharArray()){
                if(p.nextNode[c-'a'] == null){
                    p.nextNode[c-'a'] = new Tire();
                }
                p = p.nextNode[c-'a'];
            }
            p.word = word;         
        }
        return root;
    }
    
}

public class Tire{
    
    public Tire[] nextNode = new Tire[26];
    public String word;
    
}