LeetCode Entry
79. Word Search
Does grid have a word path?
79. Word Search medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/559
Problem TLDR
Does grid have a word path? #medium
Intuition
Simple Depth-First Search for every starting point will give the answer. One trick is to store visited set in a grid itself.
Approach
- Use dummy char to mark visited in a path.
- Don’t forget to restore back.
- Only mark visited right before traveling to the next to avoid failing at restoring.
Complexity
-
Time complexity: \(O(n3^n)\), n is a grid area
-
Space complexity: \(O(n)\)
Code
fun exist(board: Array<CharArray>, word: String): Boolean {
fun dfs(x: Int, y: Int, i: Int): Boolean {
if (i == word.length) return true
if (x !in 0..<board[0].size || y !in 0..<board.size) return false
val c = board[y][x]
if (c != word[i]) return false
board[y][x] = '.'
val res = dfs(x - 1, y, i + 1) || dfs(x + 1, y, i + 1)
|| dfs(x, y - 1, i + 1) || dfs(x, y + 1, i + 1)
board[y][x] = c
return res
}
for (y in 0..<board.size) for (x in 0..<board[0].size)
if (dfs(x, y, 0)) return true
return false
}
pub fn exist(mut board: Vec<Vec<char>>, word: String) -> bool {
fn dfs(mut board: &mut Vec<Vec<char>>, word: &String, x: i32, y: i32, i: usize) -> bool {
if i == word.len() { return true }
if x < 0 || y < 0 || x == board[0].len() as i32 || y == board.len() as i32 { return false }
let c = board[y as usize][x as usize];
if c as u8 != word.as_bytes()[i] { return false }
board[y as usize][x as usize] = '.';
let res =
dfs(board, word, x - 1, y, i + 1) || dfs(board, word, x + 1, y, i + 1) ||
dfs(board, word, x, y - 1, i + 1) || dfs(board, word, x, y + 1, i + 1);
board[y as usize][x as usize] = c; res
}
let (n, m) = (board.len() as i32, board[0].len() as i32);
for y in 0..n { for x in 0..m {
if dfs(&mut board, &word, x, y, 0) { return true }
}}
false
}