Word Search II
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 neighboring. The same letter cell may not be used more than once in a word.
Constraints:
- m == board.length
- n == board[i].length
- 1 <= m, n <= 12
- board[i][j] is a lowercase English letter
- 1 <= words.length <= 3 * 10^4
- 1 <= words[i].length <= 10
- words[i] consists of lowercase English letters
- All the strings of words are unique
Input Format:
- An m x n grid of characters 'board'
- An array of strings 'words'
Output Format:
- Return an array of all words from the input list that can be found on the board
Examples:
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"]
Explanation:
The words 'eat' and 'oath' can be constructed from the board.
Example 2:
Input:
board = [["a","b"],["c","d"]], words = ["abcb"]
Output:
[]
Explanation:
The word 'abcb' cannot be constructed from the board because the same letter 'b' would be used twice.
Solutions
Trie + Backtracking DFS
Use a Trie data structure to store all the words, then perform backtracking DFS from each cell on the board to find words that exist in the Trie.
Optimized Trie + Backtracking
An optimized version that prunes the Trie as words are found to reduce search space and improve efficiency.
Algorithm Walkthrough
Example input: nums = []
Step-by-step execution:
- Build a Trie with all the words: oath, pea, eat, rain
- Start DFS from cell (0,0) containing 'o'
- Follow path: o → a → t → h, which spells 'oath'
- Add 'oath' to result
- Continue searching from other cells...
- From cell (1,0) containing 'e', follow path: e → a → t, which spells 'eat'
- Add 'eat' to result
- Return ['oath', 'eat']
Hints
Hint 1
Hint 2
Hint 3
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize the Trie structure and the backtracking process on the grid.
Key visualization elements:
- current cell
- visited cells
- path
- trie structure
Similar Questions
Design Add and Search Words Data Structure
MediumDesign a data structure that supports adding new words and finding if a string matches any previously added string. Implement the WordDictionary class: WordDictionary() Initializes the object. void addWord(word) Adds word to the data structure, it can be matched later. bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.
Implement Trie (Prefix Tree)
MediumA trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker. Implement the Trie class: Trie() Initializes the trie object. void insert(String word) Inserts the string word into the trie. boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise. boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.
Word Search
MediumGiven an m x n grid of characters board and a string word, return true if word exists in the grid. The word can 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.
Implementation Notes
This problem combines Trie data structure with backtracking search. The key optimization is using a Trie to efficiently check prefixes and find words during the search.