68. Word Search
Given an m × n grid of letters board and a string word, return true if word can be traced on the board.
A word is traced by starting at any cell and repeatedly stepping to a horizontally or vertically adjacent cell, reading one letter per cell. The same cell may not be used twice in one word. Letters are case-sensitive.
Input: board = [["S","E","A","T"],["O","R","T","H"],["C","A","N","E"]], word = "SORT" Output: true
Explanation: Start at the top-left S, go down to O, then right to R and T.
Input: board = [["S","E","A","T"],["O","R","T","H"],["C","A","N","E"]], word = "THEN" Output: true
Explanation: Top-right T, down to H and E, then left to N.
Input: board = [["S","E","A","T"],["O","R","T","H"],["C","A","N","E"]], word = "SEAS" Output: false
Explanation: There is only one S, and it cannot be used twice.
Constraints
1 <= m, n <= 61 <= word.length <= 15boardandwordconsist of uppercase and lowercase English letters
Follow-up: How would you find every word from a large dictionary that appears on the board, without searching for each word separately?
💡 Hint 1
Try every cell as a starting point, then explore the four neighbours recursively while matching the next letter.
💡 Hint 2
Mark a cell as used while it is on the current path and unmark it when you backtrack, so other paths can still use it.
💡 Hint 3
Cheap pruning: if the board does not contain enough copies of some letter in word, the answer is false without any search.
Try it yourself first ✎
Solutions stick better after a real attempt. Peek when you're ready.
Approach
Backtracking DFS. First count the letters on the board; if word needs more of some letter than the board has, return false straight away (this kills the worst cases, such as a board full of A and a word ending in B). Then, from every cell, run dfs(r, c, k): the cell must be on the board and equal to word[k]. Temporarily overwrite it with a marker so the path cannot reuse it, recurse into the four neighbours for k + 1, and restore the letter afterwards. Reaching k === word.length - 1 on a matching cell means the whole word was found.
function exist(board, word) {
const rows = board.length;
const cols = board[0].length;
if (word.length > rows * cols) return false;
const count = new Map();
for (const row of board) for (const ch of row) count.set(ch, (count.get(ch) ?? 0) + 1);
for (const ch of word) {
const left = (count.get(ch) ?? 0) - 1;
if (left < 0) return false;
count.set(ch, left);
}
const dfs = (r, c, k) => {
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[k]) return false;
if (k === word.length - 1) return true;
const saved = board[r][c];
board[r][c] = '#';
const found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1) || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
board[r][c] = saved;
return found;
};
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (dfs(r, c, 0)) return true;
}
}
return false;
}class Solution {
public boolean exist(char[][] board, String word) {
int rows = board.length, cols = board[0].length;
if (word.length() > rows * cols) return false;
int[] count = new int[128];
for (char[] row : board) for (char ch : row) count[ch]++;
for (char ch : word.toCharArray()) if (--count[ch] < 0) return false;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (dfs(board, word, r, c, 0)) return true;
}
}
return false;
}
private boolean dfs(char[][] board, String word, int r, int c, int k) {
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(k)) return false;
if (k == word.length() - 1) return true;
char saved = board[r][c];
board[r][c] = '#';
boolean found = dfs(board, word, r + 1, c, k + 1) || dfs(board, word, r - 1, c, k + 1)
|| dfs(board, word, r, c + 1, k + 1) || dfs(board, word, r, c - 1, k + 1);
board[r][c] = saved;
return found;
}
}No submissions yet. Press Submit to run your code against every test.
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
function exist(board, word) {
}Run your code to see results here.