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

    文章目录

    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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    样例 2：

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    样例 3：

    输入：

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    提示：

    • 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;
    }
}

    • 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

    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) bool
	check = 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] = false
		return false
	}

	for r, row := range board {
		for c := range row {
			if check(0, r, c) {
				return true
			}
		}
	}

	return false
}

    • 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

    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;
    }
};

    • 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

    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 False
            if idx == len(word) - 1:
                return True
            visited[r][c] = True
            if 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 True
            visited[r][c] = False
            return False

        visited = [[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 True

        return False


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    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;
    }
}

    • 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

    非常感谢你阅读本文~
    欢迎【点赞】【收藏】【评论】三连走一波~
    放弃不难，但坚持一定很酷~
    希望我们大家都能每天进步一点点~
    本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~

  • 相关阅读:
    macOS系统查找被占用的端口号的操作
    Google Earth Engine（GEE）——对ndvi数据进行排序并获取倒数第二个值
    2022年web前端开发学习路线图
    部署LVS+Keepalived高可用群集（抢占模式，非抢占模式，延迟模式）
    涨姿势了，殊途同归的图片交互动效制作！
    [计算估计网络]十六、DHCP协议
    一文搞懂mysql索引底层逻辑，干货满满！
    实验四 循环结构程序设计（matlab）
    合宙AIR105(三): 定时器, 定时器中断和PWM输出
    关于一篇端口聚合配置的笔记
  • 原文地址：https://blog.csdn.net/leyi520/article/details/132713023