Back to DSA

Word Search II

hard
Acceptance: 37%
TrieBacktrackingMatrix

Given a two-dimensional grid of characters and a list of target words, find every word from the list that can be formed by tracing a path of horizontally or vertically adjacent cells on the grid. Each cell may be used at most once per word.

Examples

Example 1:
Input:board = [['p','q','r','s'],['t','u','v','w'],['x','y','z','a'],['b','c','d','e']], words = ['puy','quz','xyz','pqr']
Output:['pqr','xyz']

Hints

Related Problems

Implement Trie (Prefix Tree)mediumDesign Add and Search Words Data StructurehardMap Sum PairsmediumSubsetsmediumPermutationsmedium
00:00
import java.util.*;

class Solution {
    private int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};

    public List<String> findWords(char[][] board, String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode node = root;
            for (char c : w.toCharArray()) {
                if (node.children[c - 'a'] == null) node.children[c - 'a'] = new TrieNode();
                node = node.children[c - 'a'];
            }
            node.word = w;
        }
        List<String> result = new ArrayList<>();
        for (int i = 0; i < board.length; i++)
            for (int j = 0; j < board[0].length; j++)
                dfs(board, i, j, root, result);
        return result;
    }

    private void dfs(char[][] board, int i, int j, TrieNode node, List<String> result) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return;
        char c = board[i][j];
        if (c == '#' || node.children[c - 'a'] == null) return;
        node = node.children[c - 'a'];
        if (node.word != null) { result.add(node.word); node.word = null; }
        board[i][j] = '#';
        for (int[] d : dirs) dfs(board, i + d[0], j + d[1], node, result);
        board[i][j] = c;
    }

    class TrieNode { TrieNode[] children = new TrieNode[26]; String word; }
}
Time complexityO(m * n * 4^L)
Space complexityO(W * L)