Word Search II hard

Problem Statement

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 connected. 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: []

Steps

1. Trie Data Structure: Build a Trie (prefix tree) from the given words. A Trie efficiently stores and searches for prefixes of words. Each node in the Trie represents a character, and the path from the root to a node represents a prefix. We'll mark nodes representing the end of a word.

2. Depth-First Search (DFS): For each cell in the board, perform a DFS to explore adjacent cells. During the DFS, we'll traverse the Trie simultaneously. If we encounter a node in the Trie that represents the end of a word, we add that word to the result list.

3. Backtracking: Crucially, after exploring a cell, we need to backtrack to restore the board's original state for other paths.

4. Visited Array: Use a visited array (or set) to keep track of visited cells during DFS to avoid cycles.

Explanation

The Trie allows us to efficiently check if a prefix is valid. Instead of checking each word individually against the board, we check prefixes. The DFS systematically explores all possible paths on the board. Backtracking ensures that each cell is considered independently for different words.

Code

class Solution {
    private TrieNode root;
    private int m, n;
    private List<String> result;

    class TrieNode {
        TrieNode[] children;
        String word;

        TrieNode() {
            children = new TrieNode[26];
            word = null;
        }
    }

    private void buildTrie(String[] words) {
        root = new TrieNode();
        for (String word : words) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (node.children[index] == null) {
                    node.children[index] = new TrieNode();
                }
                node = node.children[index];
            }
            node.word = word;
        }
    }

    private void dfs(char[][] board, int i, int j, TrieNode node, boolean[][] visited) {
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || node == null) {
            return;
        }
        visited[i][j] = true;
        int index = board[i][j] - 'a';
        node = node.children[index];
        if (node != null) {
            if (node.word != null) {
                result.add(node.word);
                node.word = null; // Avoid duplicates
            }
            int[] dx = {0, 0, 1, -1};
            int[] dy = {1, -1, 0, 0};
            for (int k = 0; k < 4; k++) {
                dfs(board, i + dx[k], j + dy[k], node, visited);
            }
        }
        visited[i][j] = false; // Backtrack
    }

    public List<String> findWords(char[][] board, String[] words) {
        m = board.length;
        n = board[0].length;
        result = new ArrayList<>();
        buildTrie(words);
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, i, j, root, visited);
            }
        }
        return result;
    }
}

Complexity

• Time Complexity: O(M * N * 4^L), where M x N is the size of the board and L is the maximum length of a word. In the worst case, we explore all possible paths of length L. Trie operations are generally O(L) for searching and insertion.

• Space Complexity: O(N * M + sum of word lengths) – O(N * M) for the visited array. The Trie's space complexity depends on the sum of the lengths of all words.