专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
最近关于大疆不强制 9 点上班，强制 9 点下班的消息冲上热搜，一到晚上9点，大疆的主管和HR分三轮赶人下班，禁止员工加班，9点以后，HRBP开始扫雷式赶人，他们背着“必须清场”的KPI。深圳总部实行赶人策略，上海区域更直截了当，办公楼到晚上9点准时关灯。
而美的从上周起就开始提倡各部门领导严谨控制加班，规定18:20不允许有人还在公司加班，同时也禁止了员工就餐后再返回工位继续加班的现象。一到下班时间，HR就会挨着部门催促员工抓紧时间下班。
这么好的事早几年就应该执行，本来三个人的活硬是让两个人加班干出来，回归到8小时工作制就会多出很多岗位，现在每年有一千多万毕业大学生，实行8小时工作制也可以促进大学生就业率。
有的人可能会担心，制造行业员工的收入主要靠加班，如果没有加班，只拿基本工资，估计难以生存，我觉得吧这个事有利有弊，但我还是支持8小时工作制。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第79题：单词搜索。
问题描述
来源：LeetCode第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 = "ABCB" 输出：false
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成
问题分析
这题让判断网格中是否存在要查找的单词，也没有告诉单词的起始位置在网格中的什么地方，我们以网格中的每一个位置当做起始位置来进行搜索。题中说的相邻是指水平和垂直方向，也就是从每个位置的上下左右四个方向进行搜索。
这是一道回溯算法题，如果从某个位置开始搜索，要注意一个位置不能重复搜索，所以搜索过之后要把它标记一下，题中说了字符串仅由大小写英文字母组成，标记的字符只要不是大小写英文字母就可以。沿着某条路径搜索完之后如果没有找到，需要撤销标记。
JAVA：
public boolean exist(char[][] board, String word) { char[] chars = word.toCharArray(); // 遍历矩阵中的所有位置，以每一个位置为起始点进行查找。 for (int i = 0; i < board.length; i++) for (int j = 0; j < board[0].length; j++) { // 以位置[i,j]为起始点查找，如果找到，直接返回true。 if (dfs(board, i, j, chars, 0)) returntrue; } returnfalse; } // 方向数组 int[][] dirs = newint[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; private boolean dfs(char[][] board, int i, int j, char[] word, int index) { if (index == word.length) // 要查找字符串中的所有字符都查找完了。 returntrue; // 不能越界 if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) returnfalse; if (board[i][j] != word[index]) returnfalse; char tmp = board[i][j];// 先把当前位置的字符保存下来 board[i][j] = '#';// 修改当前位置的字符，只要不是大小写字符都可以 for (int[] dir : dirs) {// 沿着当前位置的上下左右四个方向查找。 int x = i + dir[0]; int y = j + dir[1]; // 如果有一个方向能查找成功，直接返回true if (dfs(board, x, y, word, index + 1)) returntrue; } board[i][j] = tmp;// 还原。 returnfalse; }C++：
public: bool exist(vector
> &board, string word) { // 遍历矩阵中的所有位置，以每一个位置为起始点进行查找。 for (int i = 0; i < board.size(); ++i) { for (int j = 0; j < board[0].size(); ++j) { // 以位置[i,j]为起始点查找，如果找到，直接返回true。 if (dfs(board, i, j, word, 0)) returntrue; } } returnfalse; } constint dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; private: bool dfs(vector
> &board, int i, int j, string &word, int index) { if (index == word.size()) // 要查找字符串中的所有字符都查找完了。 returntrue; // 不能越界 if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size()) returnfalse; if (board[i][j] != word[index]) returnfalse; char tmp = board[i][j];// 先把当前位置的字符保存下来 board[i][j] = '#'; // 修改当前位置的字符，只要不是大小写字符都可以 for (constauto &dir: dirs) {// 沿着当前位置的上下左右四个方向查找。 int x = i + dir[0]; int y = j + dir[1]; // 如果有一个方向能查找成功，直接返回true if (dfs(board, x, y, word, index + 1)) returntrue; } board[i][j] = tmp; // 恢复原字符 returnfalse; }
笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴