面试蔚来汽车，跪了。。。

五分钟学算法

发布于 2024-03-26 14:46:41

3350

发布于 2024-03-26 14:46:41

文章被收录于专栏：五分钟学算法

大家好，我是吴师兄。

今天看到一个小伙伴去蔚来面试的经历，虽然跪了，但经验还是值得参考的，一方面八股文考察的内容属于大众熟悉的高频知识点，另外一方面算法题还挺难的，今天来练习一下。

来看二面的算法题，题目描述是这样的。

字母迷宫游戏初始界面记作 m x n 二维字符串数组 grid，请判断玩家是否能在 grid 中找到目标单词 target。注意：寻找单词时必须按照字母顺序，通过水平或垂直方向相邻的单元格内的字母构成，同时，同一个单元格内的字母 不允许被重复使用 。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

本题的主要策略是使用深度优先搜索（DFS）。来，我们逐步拆解：

首先是主函数 wordPuzzle：

wordPuzzle 函数接收一个字符矩阵 board 和一个目标单词 word。
将目标单词转换为字符数组 words，方便逐个字符比对。
使用双层循环遍历矩阵的每一个元素，以每个元素为起点，调用 dfs 函数进行深度优先搜索。
如果在某个起点开始的搜索成功找到了目标单词，则函数返回 true；如果所有起点都搜索失败，则返回 false。

接下来是 DFS 函数：

dfs 函数是实现深度优先搜索的核心，参数包括矩阵 board、目标单词的字符数组 word、当前位置 (i, j) 和当前目标字符的索引 k。
首先检查边界条件，包括位置 (i, j) 是否越界以及当前位置的字符是否与目标字符匹配。如果不满足条件，返回 false。
如果当前字符是目标单词的最后一个字符并且匹配成功，则整个搜索过程成功，返回 true。
在当前位置上标记已访问（例如，将字符改为 #），然后递归地在四个方向上搜索下一个目标字符。
在返回之前，将当前位置的字符还原，以免影响其他路径的搜索。
返回四个方向搜索的结果的逻辑或（||），即如果任一方向搜索成功，则整体搜索成功。

简而言之，这段代码通过从矩阵的每个点出发，尝试所有可能的路径来查找目标单词。它巧妙地利用了递归和回溯，逐步深入，一旦发现当前路径不可行，就回退，尝试其他可能，直到找到一条正确的路径或确定无解。

关于 DFS ，我都会给算法训练营的同学举一个例子：

想象一下，你在一个迷宫里寻找一条路，这条路上的指示牌顺序排列能告诉你如何从起点到达终点。你需要走遍每一个岔口，尝试每条路，直到找到正确的路径。如果某条路走不通，你就返回上一个岔口，尝试其他方向。这段代码，就是在用程序的方式，帮你在字符组成的迷宫中，找到拼出目标单词的那条路。

具体代码如下：

class Solution {
    public boolean wordPuzzle(char[][] board, String word) {
        // 先将字符串进行拆分，一个一个元素进行匹配
        char[] words = word.toCharArray(); 

        // 通过两层嵌套，覆盖所有的情况
        for(int i = 0 ; i < board.length; i++) {
            for(int j = 0 ; j < board[0].length ; j++) {
                // 以该元素为起始点，递归检查是否符合要求
                if(dfs(board,words,i,j,0)) return true;
            }
        }

        return false;
       
    }

    boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        // 边界情况判断
        // 行越界
        // 列越界
        // 矩阵元素已访问过 
         if( i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;

        // 之前已经和目标字符串匹配成功了 length - 1 个字符，此时又匹配成功了最后一个元素，直接返回结果
        if( k == word.length - 1) return true;

        // 标记当前矩阵元素，将其修改为特殊字符 #  ，代表此元素已访问过，防止之后搜索时重复访问。
        board[i][j] = '#';

        // 搜索元素的四个方向 上 左 下 右，匹配下一个目标元素
        boolean res =  dfs(board,word,i,j-1,k+1) 
        || dfs(board,word,i - 1 ,j ,k + 1) 
        || dfs(board,word,i , j + 1 ,k + 1) 
        || dfs(board,word, i + 1 ,j , k + 1);
    
        // 回退时还原当前矩阵元素
        board[i][j] = word[k];

        // 返回结果
        return res;
        
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2024-03-21，如有侵权请联系 cloudcommunity@tencent.com 删除

算法