## 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` and `word` 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();
let res = false;
assert_eq!(Solution::exist(board, word), res);
let board = vec_vec_char![['A', 'C'], ['A', 'D']];
let word = "".to_string();
let res = false;
assert_eq!(Solution::exist(board, word), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.