79. Word Search
Given an m x n
board
and a word
, find if the 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.
Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true
Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" Output: true
Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" Output: false
Constraints:
m == board.length
n = board[i].length
1 <= m, n <= 200
1 <= word.length <= 103
board
andword
consists only of lowercase and uppercase English letters.
Rust Solution
struct Solution;
impl Solution {
fn exist(board: Vec<Vec<char>>, word: String) -> bool {
if let Some(mut word_search) = WordSearch::new(board, word) {
word_search.exist()
} else {
false
}
}
}
#[derive(Debug)]
struct WordSearch {
n: usize,
m: usize,
visited: Vec<Vec<bool>>,
board: Vec<Vec<char>>,
word: Vec<char>,
}
impl WordSearch {
fn new(board: Vec<Vec<char>>, word: String) -> Option<Self> {
let n = board.len();
if n == 0 {
return None;
}
let m = board[0].len();
if m == 0 {
return None;
}
if word.is_empty() {
return None;
}
let visited = vec![vec![false; m]; n];
let word = word.chars().collect();
Some(Self {
n,
m,
visited,
board,
word,
})
}
fn dfs(&mut self, i: usize, j: usize, k: usize) -> bool {
if self.visited[i][j] || self.word[k] != self.board[i][j] {
return false;
}
if k == self.word.len() - 1 {
return true;
} else {
self.visited[i][j] = true;
if (j > 0 && self.dfs(i, j - 1, k + 1))
|| (j < self.m - 1 && self.dfs(i, j + 1, k + 1))
|| (i > 0 && self.dfs(i - 1, j, k + 1))
|| (i < self.n - 1 && self.dfs(i + 1, j, k + 1))
{
return true;
}
self.visited[i][j] = false;
}
false
}
fn exist(&mut self) -> bool {
for i in 0..self.n {
for j in 0..self.m {
if self.dfs(i, j, 0) {
return true;
}
}
}
false
}
}
#[test]
fn test() {
let board = vec_vec_char![];
let word = "AC".to_string();
assert_eq!(Solution::exist(board, word), false);
let board = vec_vec_char![['A', 'C'], ['A', 'D']];
let word = "".to_string();
assert_eq!(Solution::exist(board, word), false);
}
Having problems with this solution? Click here to submit an issue on github.