Brute Force Backtracking per Word
Intuition
For each word in the list, we can perform a DFS/backtracking search on the board starting from every cell. For each starting position, we try to match the word character by character, moving to adjacent cells and marking visited cells to avoid reuse. This straightforward approach checks each word independently, which leads to a lot of repeated traversal when many words share common prefixes.
Algorithm
- For each word in the word list, iterate over all cells on the board as potential starting positions.
- From each starting cell, perform a DFS: if the current cell matches the current character of the word, mark the cell as visited and recurse in all four directions for the next character.
- If all characters are matched, add the word to the result.
- Backtrack by restoring the cell's original value.
- Return all found words.
Time
O(w * m * n * 4^l) where w is the number of words, m*n is the board size, and l is the max word lengthSpaceO(l) for the recursion stackCode (C++ · Java · Python · Go)
class Solution {
int dirs[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
bool dfs(vector<vector<char>>& board, const string& word, int i, int j, int k) {
if (k == word.size()) return true;
if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size()) return false;
if (board[i][j] != word[k]) return false;
char temp = board[i][j];
board[i][j] = '#';
for (auto& d : dirs) {
if (dfs(board, word, i + d[0], j + d[1], k + 1)) {
board[i][j] = temp;
return true;
}
}
board[i][j] = temp;
return false;
}
public:
vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
vector<string> result;
for (const string& word : words) {
bool found = false;
for (int i = 0; i < board.size() && !found; i++) {
for (int j = 0; j < board[0].size() && !found; j++) {
if (dfs(board, word, i, j, 0)) {
result.push_back(word);
found = true;
}
}
}
}
return result;
}
};class Solution {
private int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
public List<String> findWords(char[][] board, String[] words) {
List<String> result = new ArrayList<>();
for (String word : words) {
if (existsOnBoard(board, word)) {
result.add(word);
}
}
return result;
}
private boolean existsOnBoard(char[][] board, String word) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (dfs(board, word, i, j, 0)) return true;
}
}
return false;
}
private boolean dfs(char[][] board, String word, int i, int j, int k) {
if (k == word.length()) return true;
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return false;
if (board[i][j] != word.charAt(k)) return false;
char temp = board[i][j];
board[i][j] = '#';
for (int[] d : dirs) {
if (dfs(board, word, i + d[0], j + d[1], k + 1)) {
board[i][j] = temp;
return true;
}
}
board[i][j] = temp;
return false;
}
}from typing import List
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
m, n = len(board), len(board[0])
result = []
def dfs(i: int, j: int, k: int, word: str) -> bool:
if k == len(word):
return True
if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]:
return False
temp = board[i][j]
board[i][j] = "#"
for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
if dfs(i + di, j + dj, k + 1, word):
board[i][j] = temp
return True
board[i][j] = temp
return False
for word in words:
found = False
for i in range(m):
for j in range(n):
if dfs(i, j, 0, word):
result.append(word)
found = True
break
if found:
break
return resultfunc findWords(board [][]byte, words []string) []string {
dirs := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
m, n := len(board), len(board[0])
result := []string{}
var dfs func(i, j, k int, word string) bool
dfs = func(i, j, k int, word string) bool {
if k == len(word) {
return true
}
if i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word[k] {
return false
}
temp := board[i][j]
board[i][j] = '#'
for _, d := range dirs {
if dfs(i+d[0], j+d[1], k+1, word) {
board[i][j] = temp
return true
}
}
board[i][j] = temp
return false
}
for _, word := range words {
found := false
for i := 0; i < m && !found; i++ {
for j := 0; j < n && !found; j++ {
if dfs(i, j, 0, word) {
result = append(result, word)
found = true
}
}
}
}
return result
}