Word Search II
Problem for Word Search II
You are given a 2D grid of letters (board) and a list of words. Your goal is to find all the words from the list that can be formed by following a continuous path on the grid.
A word is considered valid if its letters can be connected using adjacent cells in the grid, either horizontally or vertically. However, you cannot use the same cell more than once while forming a word. Return all the words from the list that meet these conditions.
Example 1:
Input:
board = [
["a","b","c","d"],
["s","a","a","t"],
["a","c","k","e"],
["a","c","d","n"]
],
words = ["bat","cat","back","backend","stack"]
Output: ["cat","back","backend"]
board = [
["a","b","c","d"],
["s","a","a","t"],
["a","c","k","e"],
["a","c","d","n"]
],
words = ["bat","cat","back","backend","stack"]
Output: ["cat","back","backend"]
Example 2:
Input:
board = [
["x","o"],
["x","o"]
],
words = ["xoxo"]
Output: []
board = [
["x","o"],
["x","o"]
],
words = ["xoxo"]
Output: []
Constraints:
- 1 <= board.length, board[i].length <= 10
- board[i] consists only of lowercase English letter.
- 1 <= words.length <= 100
- 1 <= words[i].length <= 10
- words[i] consists only of lowercase English letters.
- All strings within words are distinct.
Word Search II Solution
Recommendation for Time and Space Complexity – Target O(m * n * 4 * (3^(t-1)) + s) time and O(s) space, where:
- m, n: Grid dimensions.
- t: Longest word length.
- s: Total word lengths.
Hints for solving problems
Hint 1 :
Use backtracking to search for a word by recursively matching characters from each grid cell. However, running backtracking separately for all words is inefficient. Can you optimize this with a better data structure?
Hint 2 :
Insert all words into a Trie. Traverse the grid once, starting from each cell. If a cell matches a Trie node, continue searching; otherwise, stop. When you reach an “end of word” in the Trie, you’ve found a valid word.
Hint 3 :
Store word indices in Trie nodes to quickly retrieve words during the search. Add the word to the result list when found, and mark its index as used to prevent duplicates.
Hint 4 :
Insert all words into the Trie, then explore the grid. Match characters recursively using the Trie. Add words to the result upon finding a match, and continue exploring other paths to find all possible words.
There are mainly 3 approach to solve this problem-
- Backtracking Method
- Backtracking(Trie + Hash Set) Method
- Backtracking(Trie) Method
1. Backtracking Method
Search each word by exploring all paths in the grid using backtracking. This method is simple but inefficient for large inputs due to repeated searches.
- Time complexity: O(m * n * 4^t + s)
- Space complexity: O(t)
where m is the number of rows, n is the number of columns, t is the maximum length of any word in the array words and s is the sum of the lengths of all the words.
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
vector findWords(vector<vector<char>>& board, vector<string>& words) {
int ROWS = board.size(), COLS = board[0].size();
vector res;
for (string& word : words) {
bool flag = false;
for (int r = 0; r < ROWS && !flag; r++) {
for (int c = 0; c < COLS; c++) {
if (board[r][c] != word[0]) continue;
if (backtrack(board, r, c, word, 0)) {
res.push_back(word);
flag = true;
break;
}
}
}
}
return res;
}
private:
bool backtrack(vector<vector<char>>& board, int r, int c, string& word, int i) {
if (i == word.length()) return true;
if (r < 0 || c < 0 || r >= board.size() ||
c >= board[0].size() || board[r][c] != word[i])
return false;
board[r][c] = '*';
bool ret = backtrack(board, r + 1, c, word, i + 1) ||
backtrack(board, r - 1, c, word, i + 1) ||
backtrack(board, r, c + 1, word, i + 1) ||
backtrack(board, r, c - 1, word, i + 1);
board[r][c] = word[i];
return ret;
}
};
Java
public class Solution {
public List<String> findWords(char[][] board, String[] words) {
int ROWS = board.length, COLS = board[0].length;
List res = new ArrayList<>();
for (String word : words) {
boolean flag = false;
for (int r = 0; r < ROWS && !flag; r++) {
for (int c = 0; c < COLS; c++) {
if (board[r][c] != word.charAt(0)) continue;
if (backtrack(board, r, c, word, 0)) {
res.add(word);
flag = true;
break;
}
}
}
}
return res;
}
private boolean backtrack(char[][] board, int r, int c, String word, int i) {
if (i == word.length()) return true;
if (r < 0 || c < 0 || r >= board.length ||
c >= board[0].length || board[r][c] != word.charAt(i))
return false;
board[r][c] = '*';
boolean ret = backtrack(board, r + 1, c, word, i + 1) ||
backtrack(board, r - 1, c, word, i + 1) ||
backtrack(board, r, c + 1, word, i + 1) ||
backtrack(board, r, c - 1, word, i + 1);
board[r][c] = word.charAt(i);
return ret;
}
}
Python
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
ROWS, COLS = len(board), len(board[0])
res = []
def backtrack(r, c, i):
if i == len(word):
return True
if (r < 0 or c < 0 or r >= ROWS or
c >= COLS or board[r][c] != word[i]
):
return False
board[r][c] = '*'
ret = (backtrack(r + 1, c, i + 1) or
backtrack(r - 1, c, i + 1) or
backtrack(r, c + 1, i + 1) or
backtrack(r, c - 1, i + 1))
board[r][c] = word[i]
return ret
for word in words:
flag = False
for r in range(ROWS):
if flag:
break
for c in range(COLS):
if board[r][c] != word[0]:
continue
if backtrack(r, c, 0):
res.append(word)
flag = True
break
return res
JavaScript
class Solution {
/**
* @param {character[][]} board
* @param {string[]} words
* @return {string[]}
*/
findWords(board, words) {
const ROWS = board.length, COLS = board[0].length;
const res = [];
const backtrack = (r, c, word, i) => {
if (i === word.length) return true;
if (r < 0 || c < 0 || r >= ROWS ||
c >= COLS || board[r][c] !== word[i]) return false;
const temp = board[r][c];
board[r][c] = '*';
const ret = backtrack(r + 1, c, word, i + 1) ||
backtrack(r - 1, c, word, i + 1) ||
backtrack(r, c + 1, word, i + 1) ||
backtrack(r, c - 1, word, i + 1);
board[r][c] = temp;
return ret;
};
for (const word of words) {
let flag = false;
for (let r = 0; r < ROWS; r++) {
if (flag) break;
for (let c = 0; c < COLS; c++) {
if (board[r][c] !== word[0]) continue;
if (backtrack(r, c, word, 0)) {
res.push(word);
flag = true;
break;
}
}
}
}
return res;
}
}
2. Backtracking(Trie + Hash Set) Method
Use a Trie to store words and a Hash Set to track found words. Backtracking checks characters in the Trie, adding valid words to the result set to improve efficiency.
- Time complexity: <latex>O\left ( m\times n \times 4 \times 3^{t-1} + s\right )</latex>.
- Space complexity: O(s)
where m is the number of rows, n is the number of columns, t is the maximum length of any word in the array words and s is the sum of the lengths of all the words.
Code
C++
Java
Python
JavaScript
C++
class TrieNode {
public:
unordered_map<char, TrieNode*> children;
bool isWord;
TrieNode() : isWord(false) {}
void addWord(const string& word) {
TrieNode* cur = this;
for (char c : word) {
if (!cur->children.count(c)) {
cur->children[c] = new TrieNode();
}
cur = cur->children[c];
}
cur->isWord = true;
}
};
class Solution {
unordered_set<string> res;
vector<vector<bool>> visit;
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
TrieNode* root = new TrieNode();
for (const string& word : words) {
root->addWord(word);
}
int ROWS = board.size(), COLS = board[0].size();
visit.assign(ROWS, vector<bool>(COLS, false));
for (int r = 0; r < ROWS; ++r) {
for (int c = 0; c < COLS; ++c) {
dfs(board, r, c, root, "");
}
}
return vector<string>(res.begin(), res.end());
}
private:
void dfs(vector<vector<char>>& board, int r, int c, TrieNode* node, string word) {
int ROWS = board.size(), COLS = board[0].size();
if (r < 0 || c < 0 || r >= ROWS ||
c >= COLS || visit[r][c] ||
!node->children.count(board[r][c])) {
return;
}
visit[r][c] = true;
node = node->children[board[r][c]];
word += board[r][c];
if (node->isWord) {
res.insert(word);
}
dfs(board, r + 1, c, node, word);
dfs(board, r - 1, c, node, word);
dfs(board, r, c + 1, node, word);
dfs(board, r, c - 1, node, word);
visit[r][c] = false;
}
};
Java
public class TrieNode {
Map<Character, TrieNode> children;
boolean isWord;
public TrieNode() {
children = new HashMap<>();
isWord = false;
}
public void addWord(String word) {
TrieNode cur = this;
for (char c : word.toCharArray()) {
cur.children.putIfAbsent(c, new TrieNode());
cur = cur.children.get(c);
}
cur.isWord = true;
}
}
public class Solution {
private Set<String> res;
private boolean[][] visit;
public List<String> findWords(char[][] board, String[] words) {
TrieNode root = new TrieNode();
for (String word : words) {
root.addWord(word);
}
int ROWS = board.length, COLS = board[0].length;
res = new HashSet<>();
visit = new boolean[ROWS][COLS];
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
dfs(board, r, c, root, "");
}
}
return new ArrayList<>(res);
}
private void dfs(char[][] board, int r, int c, TrieNode node, String word) {
int ROWS = board.length, COLS = board[0].length;
if (r < 0 || c < 0 || r >= ROWS ||
c >= COLS || visit[r][c] ||
!node.children.containsKey(board[r][c])) {
return;
}
visit[r][c] = true;
node = node.children.get(board[r][c]);
word += board[r][c];
if (node.isWord) {
res.add(word);
}
dfs(board, r + 1, c, node, word);
dfs(board, r - 1, c, node, word);
dfs(board, r, c + 1, node, word);
dfs(board, r, c - 1, node, word);
visit[r][c] = false;
}
}
Python
class TrieNode:
def __init__(self):
self.children = {}
self.isWord = False
def addWord(self, word):
cur = self
for c in word:
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.isWord = True
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = TrieNode()
for w in words:
root.addWord(w)
ROWS, COLS = len(board), len(board[0])
res, visit = set(), set()
def dfs(r, c, node, word):
if (r < 0 or c < 0 or r >= ROWS or
c >= COLS or (r, c) in visit or
board[r][c] not in node.children
):
return
visit.add((r, c))
node = node.children[board[r][c]]
word += board[r][c]
if node.isWord:
res.add(word)
dfs(r + 1, c, node, word)
dfs(r - 1, c, node, word)
dfs(r, c + 1, node, word)
dfs(r, c - 1, node, word)
visit.remove((r, c))
for r in range(ROWS):
for c in range(COLS):
dfs(r, c, root, "")
return list(res)
JavaScript
class TrieNode {
constructor() {
this.children = {};
this.isWord = false;
}
/**
* @param {string} word
* @return {void}
*/
addWord(word) {
let cur = this;
for (const c of word) {
if (!(c in cur.children)) {
cur.children[c] = new TrieNode();
}
cur = cur.children[c];
}
cur.isWord = true;
}
}
class Solution {
/**
* @param {character[][]} board
* @param {string[]} words
* @return {string[]}
*/
findWords(board, words) {
const root = new TrieNode();
for (const word of words) {
root.addWord(word);
}
const ROWS = board.length, COLS = board[0].length;
const res = new Set(), visit = new Set();
const dfs = (r, c, node, word) => {
if (r < 0 || c < 0 || r >= ROWS ||
c >= COLS || visit.has(`${r},${c}`) ||
!(board[r][c] in node.children)) {
return;
}
visit.add(`${r},${c}`);
node = node.children[board[r][c]];
word += board[r][c];
if (node.isWord) {
res.add(word);
}
dfs(r + 1, c, node, word);
dfs(r - 1, c, node, word);
dfs(r, c + 1, node, word);
dfs(r, c - 1, node, word);
visit.delete(`${r},${c}`);
};
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
dfs(r, c, root, "");
}
}
return Array.from(res);
}
}
3. Backtracking(Trie) Method
Use a Trie to store words and a Hash Set to track found words. Backtracking checks characters in the Trie, adding valid words to the result set to improve efficiency.
- Time complexity: O(m * n * 4t * 3^(t-1) + s).
- Space complexity: O(s)
where m is the number of rows, n is the number of columns, t is the maximum length of any word in the array words and s is the sum of the lengths of all the words.
Code
C++
Java
Python
JavaScript
C++
class TrieNode {
public:
TrieNode* children[26];
int idx;
int refs;
TrieNode() {
for (int i = 0; i < 26; ++i) { children[i] = nullptr; } idx = -1; refs = 0; } void addWord(const string& word, int i) { TrieNode* cur = this; cur->refs++;
for (char c : word) {
int index = c - 'a';
if (!cur->children[index]) {
cur->children[index] = new TrieNode();
}
cur = cur->children[index];
cur->refs++;
}
cur->idx = i;
}
};
class Solution {
public:
vector<string> res;
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
TrieNode* root = new TrieNode();
for (int i = 0; i < words.size(); ++i) { root->addWord(words[i], i);
}
for (int r = 0; r < board.size(); ++r) {
for (int c = 0; c < board[0].size(); ++c) {
dfs(board, root, r, c, words);
}
}
return res;
}
void dfs(auto& board, TrieNode* node, int r, int c, auto& words) {
if (r < 0 || c < 0 || r >= board.size() ||
c >= board[0].size() || board[r][c] == '*' ||
!node->children[board[r][c] - 'a']) {
return;
}
char temp = board[r][c];
board[r][c] = '*';
TrieNode* prev = node;
node = node->children[temp - 'a'];
if (node->idx != -1) {
res.push_back(words[node->idx]);
node->idx = -1;
node->refs--;
if (!node->refs) {
prev->children[temp - 'a'] = nullptr;
node = nullptr;
board[r][c] = temp;
return;
}
}
dfs(board, node, r + 1, c, words);
dfs(board, node, r - 1, c, words);
dfs(board, node, r, c + 1, words);
dfs(board, node, r, c - 1, words);
board[r][c] = temp;
}
};
Java
public class TrieNode {
TrieNode[] children = new TrieNode[26];
int idx = -1;
int refs = 0;
public void addWord(String word, int i) {
TrieNode cur = this;
cur.refs++;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (cur.children[index] == null) {
cur.children[index] = new TrieNode();
}
cur = cur.children[index];
cur.refs++;
}
cur.idx = i;
}
}
public class Solution {
List<String> res = new ArrayList<>();
public List<String> findWords(char[][] board, String[] words) {
TrieNode root = new TrieNode();
for (int i = 0; i < words.length; i++) {
root.addWord(words[i], i);
}
for (int r = 0; r < board.length; r++) {
for (int c = 0; c < board[0].length; c++) {
dfs(board, root, r, c, words);
}
}
return res;
}
private void dfs(char[][] board, TrieNode node, int r, int c, String[] words) {
if (r < 0 || c < 0 || r >= board.length ||
c >= board[0].length || board[r][c] == '*' ||
node.children[board[r][c] - 'a'] == null) {
return;
}
char temp = board[r][c];
board[r][c] = '*';
TrieNode prev = node;
node = node.children[temp - 'a'];
if (node.idx != -1) {
res.add(words[node.idx]);
node.idx = -1;
node.refs--;
if (node.refs == 0) {
node = null;
prev.children[temp - 'a'] = null;
board[r][c] = temp;
return;
}
}
dfs(board, node, r + 1, c, words);
dfs(board, node, r - 1, c, words);
dfs(board, node, r, c + 1, words);
dfs(board, node, r, c - 1, words);
board[r][c] = temp;
}
}
Python
class TrieNode:
def __init__(self):
self.children = [None] * 26
self.idx = -1
self.refs = 0
def addWord(self, word, i):
cur = self
cur.refs += 1
for c in word:
index = ord(c) - ord('a')
if not cur.children[index]:
cur.children[index] = TrieNode()
cur = cur.children[index]
cur.refs += 1
cur.idx = i
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = TrieNode()
for i in range(len(words)):
root.addWord(words[i], i)
ROWS, COLS = len(board), len(board[0])
res = []
def getIndex(c):
index = ord(c) - ord('a')
return index
def dfs(r, c, node):
if (r < 0 or c < 0 or r >= ROWS or
c >= COLS or board[r][c] == '*' or
not node.children[getIndex(board[r][c])]):
return
tmp = board[r][c]
board[r][c] = '*'
prev = node
node = node.children[getIndex(tmp)]
if node.idx != -1:
res.append(words[node.idx])
node.idx = -1
node.refs -= 1
if not node.refs:
prev.children[getIndex(tmp)] = None
node = None
board[r][c] = tmp
return
dfs(r + 1, c, node)
dfs(r - 1, c, node)
dfs(r, c + 1, node)
dfs(r, c - 1, node)
board[r][c] = tmp
for r in range(ROWS):
for c in range(COLS):
dfs(r, c, root)
return res
JavaScript
class TrieNode {
constructor() {
this.children = Array(26).fill(null);
this.idx = -1;
this.refs = 0;
}
/**
* @param {string} word
* @param {number} i
* @return {void}
*/
addWord(word, i) {
let cur = this;
cur.refs++;
for (const c of word) {
const index = c.charCodeAt(0) - 'a'.charCodeAt(0);
if (cur.children[index] === null) {
cur.children[index] = new TrieNode();
}
cur = cur.children[index];
cur.refs++;
}
cur.idx = i;
}
}
class Solution {
/**
* @param {character[][]} board
* @param {string[]} words
* @return {string[]}
*/
findWords(board, words) {
const root = new TrieNode();
for (let i = 0; i < words.length; i++) {
root.addWord(words[i], i);
}
const ROWS = board.length, COLS = board[0].length;
const res = [];
const dfs = (r, c, node) => {
if (r < 0 || c < 0 || r >= ROWS ||
c >= COLS || board[r][c] === '*' ||
node.children[this.getId(board[r][c])] === null) {
return;
}
let tmp = board[r][c];
board[r][c] = '*';
let prev = node;
node = node.children[this.getId(tmp)];
if (node.idx !== -1) {
res.push(words[node.idx]);
node.idx = -1;
node.refs--;
if (node.refs === 0) {
prev.children[this.getId(tmp)] = null;
node = null;
board[r][c] = tmp;
return ;
}
}
dfs(r + 1, c, node);
dfs(r - 1, c, node);
dfs(r, c + 1, node);
dfs(r, c - 1, node);
board[r][c] = tmp;
};
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
dfs(r, c, root);
}
}
return Array.from(res);
}
/**
* @param {string} c
* @return {number}
*/
getId(c) {
return c.charCodeAt(0) - 'a'.charCodeAt(0);
}
}
