1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159
//! Word Search [leetcode: word_search](https://leetcode.com/problems/word-search/) //! //! Given a 2D board and a word, find if the word exists in the grid. //! //! The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. //! //! **Example 1:** //! ``` //! board = //! [ //! ['A','B','C','E'], //! ['S','F','C','S'], //! ['A','D','E','E'] //! ] //! //! Given word = "ABCCED", return true. //! Given word = "SEE", return true. //! Given word = "ABCB", return false. //! ``` //! /// # Solutions /// /// # Approach 1: DFS /// /// * Time complexity: /// /// * Space complexity: /// /// * Runtime: 8 ms /// * Memory: 3.5 MB /// /// ```rust /// impl Solution { /// const DIRS: [[i32; 2]; 4] = [[1, 0], [-1, 0], [0, 1], [0, -1]]; /// /// pub fn exist(mut board: Vec<Vec<char>>, word: String) -> bool { /// if board.is_empty() || board[0].is_empty() { return false; } /// if word.is_empty() { return true; } /// /// let m = board.len(); /// let n = board[0].len(); /// let word: Vec<char> = word.chars().collect(); /// let mut used = vec![vec![false; n]; m]; /// /// for i in 0..m { /// for j in 0..n { /// if Self::dfs(&board, &word, &mut used, i, j) { return true; } /// } /// } /// /// false /// } /// /// pub fn dfs(board: &Vec<Vec<char>>, /// word: &[char], /// used: &mut Vec<Vec<bool>>, /// i: usize, /// j: usize) -> bool { /// if i >= board.len() || j >= board[0].len() || used[i][j] { return false; } /// /// if board[i][j] != word[0] { return false; } /// if word.len() == 1 { return true; } /// /// used[i][j] = true; /// for d in Self::DIRS.iter() { /// let ni = (i as i32 + d[0]) as usize; /// let nj = (j as i32 + d[1]) as usize; /// if Self::dfs(board, &word[1..], used, ni, nj) { return true; } /// } /// used[i][j] = false; /// false /// } /// } /// ``` /// /// # Approach 2: DFS /// /// * Time complexity: /// /// * Space complexity: /// /// * Runtime: 8 ms /// * Memory: 3.4 MB /// /// ```rust /// impl Solution { /// const DIRS: [[i32; 2]; 4] = [[1, 0], [-1, 0], [0, 1], [0, -1]]; /// /// pub fn exist(mut board: Vec<Vec<char>>, word: String) -> bool { /// let (height, width) = (board.len(), board[0].len()); /// if height == 0 || width == 0 || word.len() < 1 { return false } /// let seq: Vec<char> = word.chars().collect(); /// /// for row in 0..height { /// for col in 0..width { /// if board[row][col] == seq[0] && Self::dfs(&mut board, &seq, row, col, 0) { /// return true /// } /// } /// } /// false /// } /// /// fn dfs(board: &mut Vec<Vec<char>>, seq: &[char], row: usize, col: usize, count: i32) -> bool { /// if count == seq.len() as i32 { return true; } /// if row >= board.len() || col >= board[0].len() || board[row][col] != seq[count as usize] { return false; } /// /// let ch = board[row][col]; /// board[row][col] = '#'; /// for d in Self::DIRS.iter() { /// let ni = (row as i32 + d[0]) as usize; /// let nj = (col as i32 + d[1]) as usize; /// if Self::dfs(board, seq, ni, nj, count+1) { return true; } /// } /// board[row][col] = ch; /// false /// } /// } /// ``` /// pub fn exist(board: Vec<Vec<char>>, word: String) -> bool { if board.is_empty() || board[0].is_empty() { return false; } if word.is_empty() { return true; } let m = board.len(); let n = board[0].len(); let word: Vec<char> = word.chars().collect(); let mut used = vec![vec![false; n]; m]; for i in 0..m { for j in 0..n { if dfs(&board, &word, &mut used, i, j) { return true; } } } false } const DIRS: [[i32; 2]; 4] = [[1, 0], [-1, 0], [0, 1], [0, -1]]; pub fn dfs(board: &Vec<Vec<char>>, word: &[char], used: &mut Vec<Vec<bool>>, i: usize, j: usize) -> bool { if i >= board.len() || j >= board[0].len() || used[i][j] { return false; } if board[i][j] != word[0] { return false; } if word.len() == 1 { return true; } used[i][j] = true; for d in DIRS.iter() { let ni = (i as i32 + d[0]) as usize; let nj = (j as i32 + d[1]) as usize; if dfs(board, &word[1..], used, ni, nj) { return true; } } used[i][j] = false; false }