79. Word Search Medium

1/**
2 * [79] Word Search
3 *
4 * Given an m x n grid of characters board and a string word, return true if word exists in the grid.
5 * 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.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2020/11/04/word2.jpg" style="width: 322px; height: 242px;" />
9 * Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
10 * Output: true
11 *
12 * Example 2:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2020/11/04/word-1.jpg" style="width: 322px; height: 242px;" />
14 * Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
15 * Output: true
16 *
17 * Example 3:
18 * <img alt="" src="https://assets.leetcode.com/uploads/2020/10/15/word3.jpg" style="width: 322px; height: 242px;" />
19 * Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
20 * Output: false
21 *
22 *  
23 * Constraints:
24 *
25 * m == board.length
26 * n = board[i].length
27 * 1 <= m, n <= 6
28 * 1 <= word.length <= 15
29 * board and word consists of only lowercase and uppercase English letters.
30 *
31 *  
32 * Follow up: Could you use search pruning to make your solution faster with a larger board?
33 *
34 */
35pub struct Solution {}
36
37// problem: https://leetcode.com/problems/word-search/
38// discuss: https://leetcode.com/problems/word-search/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41
42impl Solution {
43    const DIRECTIONS: [(i32, i32); 4] = [(0, 1), (0, -1), (-1, 0), (1, 0)];
44    pub fn exist(board: Vec<Vec<char>>, word: String) -> bool {
45        for i in 0..board.len() {
46            for j in 0..board[0].len() {
47                if Self::search(
48                    &board,
49                    &mut vec![vec![false; board[0].len()]; board.len()],
50                    0,
51                    &word.chars().collect::<Vec<char>>(),
52                    (i as i32, j as i32),
53                ) {
54                    return true;
55                }
56            }
57        }
58        false
59    }
60
61    fn search(
62        board: &Vec<Vec<char>>,
63        visited: &mut Vec<Vec<bool>>,
64        current: usize,
65        word: &Vec<char>,
66        index: (i32, i32),
67    ) -> bool {
68        if current == word.len() {
69            return true;
70        } else if current > word.len() {
71            return false;
72        }
73
74        if index.0 < 0
75            || index.1 < 0
76            || index.0 >= board.len() as i32
77            || index.1 >= board[0].len() as i32
78            || board[index.0 as usize][index.1 as usize] != word[current]
79            || visited[index.0 as usize][index.1 as usize]
80        {
81            return false;
82        }
83
84        visited[index.0 as usize][index.1 as usize] = true;
85        for d in Self::DIRECTIONS {
86            if Self::search(
87                board,
88                visited,
89                current + 1,
90                word,
91                (index.0 + d.0, index.1 + d.1),
92            ) {
93                return true;
94            }
95        }
96        visited[index.0 as usize][index.1 as usize] = false;
97        false
98    }
99}
100
101// submission codes end
102
103#[cfg(test)]
104mod tests {
105    use super::*;
106
107    #[test]
108    fn test_79() {
109        assert!(Solution::exist(
110            vec![
111                vec!['A', 'B', 'C', 'E'],
112                vec!['S', 'F', 'C', 'S'],
113                vec!['A', 'D', 'E', 'E']
114            ],
115            "ABCCED".to_string()
116        ));
117    }
118}
119