当前位置：首页 > news >正文

算法leetcode｜79. 单词搜索（rust重拳出击）

news 2025/8/24 6:45:15

文章目录

79. 单词搜索：
- 样例 1：
- 样例 2：
- 样例 3：
- 提示：
- 进阶：
分析：
题解：
- rust：
- go：
- c++：
- python：
- java：

79. 单词搜索：

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

样例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"输出：true

样例 2：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"输出：true

样例 3：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"输出：false

提示：

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成

进阶：

你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

分析：

面对这道算法题目，二当家的再次陷入了沉思。
需要尝试所有的可能，遍历是不可少的，使用循环或者递归，递归是首选，因为比较容易实现，深度优先，回溯，递归套娃大法好。
需要遍历每一个元素，然后开始从每个位置使用递归套娃大法，分别向上，下，左，右四个方向进行递归，重复操作，直到匹配成功，或者匹配失败就回溯尝试其他，需要注意的是不走重复的位置，所以需要一个结构标记已经走过的位置，使用和原二维字符网格相同大小的结构比较容易，空间上应该还可以优化，但是没有深究，因为空间上并没有浪费，如果做优化，肯定是以牺牲效率为代价，所谓时间换空间，我不要换。

题解：

rust：

impl Solution {pub fn exist(board: Vec<Vec<char>>, word: String) -> bool {fn check(board: &Vec<Vec<char>>, word: &Vec<char>, idx: usize, visited: &mut Vec<Vec<bool>>, r: usize, c: usize) -> bool {if r >= visited.len() || c >= visited[0].len() || visited[r][c] || board[r][c] != word[idx] {return false;}if idx == word.len() - 1 {// 完全匹配return true;}visited[r][c] = true;// 上下左右递归套娃大法if check(board, word, idx + 1, visited, r - 1, c)|| check(board, word, idx + 1, visited, r + 1, c)|| check(board, word, idx + 1, visited, r, c - 1)|| check(board, word, idx + 1, visited, r, c + 1){return true;}visited[r][c] = false;return false;}let word = word.chars().collect::<Vec<_>>();let mut visited = vec![vec![false; board[0].len()]; board.len()];for r in 0..board.len() {for c in 0..board[0].len() {if check(&board, &word, 0, &mut visited, r, c) {return true;}}}return false;}
}

go：

func exist(board [][]byte, word string) bool {visited := make([][]bool, len(board))for i := range visited {visited[i] = make([]bool, len(board[0]))}var check func(idx, r, c int) boolcheck = func(idx, r, c int) bool {if r < 0 || r >= len(board) || c < 0 || c >= len(board[0]) || visited[r][c] || board[r][c] != word[idx] {return false}if idx == len(word)-1 {// 完全匹配return true}visited[r][c] = true// 上下左右递归套娃大法if check(idx+1, r-1, c) || check(idx+1, r+1, c) || check(idx+1, r, c-1) || check(idx+1, r, c+1) {return true}visited[r][c] = falsereturn false}for r, row := range board {for c := range row {if check(0, r, c) {return true}}}return false
}

c++：

class Solution {
private:bool check(vector<vector<char>>& board, string& word, int idx, vector<vector<bool>>& visited, int r, int c) {if (r < 0 || r >= visited.size() || c < 0 || c >= visited[0].size() || visited[r][c] || board[r][c] != word[idx]) {return false;}if (idx == word.size() - 1) {// 完全匹配return true;}visited[r][c] = true;// 上下左右递归套娃大法if (check(board, word, idx + 1, visited, r - 1, c)|| check(board, word, idx + 1, visited, r + 1, c)|| check(board, word, idx + 1, visited, r, c - 1)|| check(board, word, idx + 1, visited, r, c + 1)) {return true;}visited[r][c] = false;return false;}
public:bool exist(vector<vector<char>>& board, string word) {vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));for (int r = 0; r < board.size(); ++r) {for (int c = 0; c < board[0].size(); ++c) {if (check(board, word, 0, visited, r, c)) {return true;}}}return false;}
};

python：

class Solution:def exist(self, board: List[List[str]], word: str) -> bool:def check(idx: int, r: int, c: int) -> bool:if r < 0 or r >= len(board) or c < 0 or c >= len(board[0]) or visited[r][c] or board[r][c] != word[idx]:return Falseif idx == len(word) - 1:return Truevisited[r][c] = Trueif check(idx + 1, r - 1, c) or check(idx + 1, r + 1, c) or check(idx + 1, r, c - 1) or check(idx + 1, r, c + 1):return Truevisited[r][c] = Falsereturn Falsevisited = [[False] * len(board[0]) for _ in range(len(board))]for r in range(len(board)):for c in range(len(board[0])):if check(0, r, c):return Truereturn False

java：

class Solution {public boolean exist(char[][] board, String word) {boolean[][] visited = new boolean[board.length][board[0].length];for (int r = 0; r < board.length; ++r) {for (int c = 0; c < board[0].length; ++c) {if (check(board, word, 0, visited, r, c)) {return true;}}}return false;}private boolean check(char[][] board, String word, int idx, boolean[][] visited, int r, int c) {if (r < 0 || r >= visited.length || c < 0 || c >= visited[0].length || visited[r][c] || board[r][c] != word.charAt(idx)) {return false;}if (idx == word.length() - 1) {// 完全匹配return true;}visited[r][c] = true;// 上下左右递归套娃大法if (check(board, word, idx + 1, visited, r - 1, c)|| check(board, word, idx + 1, visited, r + 1, c)|| check(board, word, idx + 1, visited, r, c - 1)|| check(board, word, idx + 1, visited, r, c + 1)) {return true;}visited[r][c] = false;return false;}
}