Word Search II
Problem Description
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.lengthn == board[i].length1 <= m, n <= 12board[i][j]is a lowercase English letter.1 <= words.length <= 3 * 1041 <= words[i].length <= 10words[i]consists of lowercase English letters.- All the strings of
wordsare unique.
Solve it on LeetCode
Approaches
1. Brute Force Approach
Intuition:
In the brute force approach, we iterate over each word and place it character by character on the board, starting from every potential starting point. This involves a depth-first search (DFS) from each cell for each word and checking all four possible directions. This naive method helps understand the base working but lacks efficiency.
Code:
- Time Complexity: O(N * M * 4^L)), where (N * M) is the size of the board, and (L) is the length of the longest word.
- Space Complexity: O(L), recursion depth for backtracking.
2. Backtracking with Trie
Intuition:
To optimize, we use a Trie data structure for efficient prefix checking. Trie allows us to minimize unnecessary DFS calls by terminating branches early if a prefix leads to no valid word. For each starting point on the board, we search using the trie to construct words, reducing redundant operations considerably compared to checking each word independently.
Code:
- Time Complexity: O(N * M * 4^L), but often faster in practice due to trie pruning.
- Space Complexity: O(N * M + W * L), where (W) is the number of words and (L) is the average word length (Trie size).