跳转至

79. 单词搜索

难度：中等

题目

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

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

示例 1：

Example-1

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

示例 2：

Example-2

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

示例 3：

Example-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 更大的情况下可以更快解决问题？

Reference

题解

使用深度优先算法，在二维数组中寻找单词第一个字母出现的位置，对于每个出现位置：

  • 将当前位置标志为经历过
  • 寻找当前位置附近满足如下条件的单元格
    1. 单元格中的字母等于单词的下一个字母
    2. 单元格未被遍历过
  • 如果找不到单元格，意味着二维数组中无法找到目标单词
  • 如果找到一个或多个单元格，则前进到下一个单元格继续进行匹配
  • 如果单词的最后一个字母成功匹配，意味着匹配成功
bool dfs(char **board, int boardSize, int* boardColSize, char *word, int posX, int posY, int **map)
{
    if (*word == 0)
        return true;
    bool ret = false;
    if (posX > 0 && board[posX - 1][posY] == *word && map[posX - 1][posY] == 0)
    {
        map[posX - 1][posY] = 1;
        ret = ret || dfs(board, boardSize, boardColSize, word + 1, posX - 1, posY, map);
        map[posX - 1][posY] = 0;
    }
    if (posX < boardSize - 1 && board[posX + 1][posY] == *word && map[posX + 1][posY] == 0)
    {
        map[posX + 1][posY] = 1;
        ret = ret || dfs(board, boardSize, boardColSize, word + 1, posX + 1, posY, map);
        map[posX + 1][posY] = 0;
    }
    if (posY > 0 && board[posX][posY - 1] == *word && map[posX][posY - 1] == 0)
    {
        map[posX][posY - 1] = 1;
        ret = ret || dfs(board, boardSize, boardColSize, word + 1, posX, posY - 1, map);
        map[posX][posY - 1] = 0;
    }
    if (posY < boardColSize[0] - 1 && board[posX][posY + 1] == *word && map[posX][posY + 1] == 0)
    {
        map[posX][posY + 1] = 1;
        ret = ret || dfs(board, boardSize, boardColSize, word + 1, posX, posY + 1, map);
        map[posX][posY + 1] = 0;
    }
    return ret;
}
bool exist(char** board, int boardSize, int* boardColSize, char * word){
    bool ret = false;
    int i = 0, j = 0, **map = (int **)malloc(sizeof(int *) * boardSize);
    for (i = 0; i < boardSize; i++)
        map[i] = (int *)memset(malloc(sizeof(int) * boardColSize[i]), 0, sizeof(int) * boardColSize[i]);
    for (i = 0; i < boardSize && !ret; i++)
    {
        for (j = 0; j < boardColSize[0] && !ret; j++)
        {
            if (board[i][j] == *word)
            {
                map[i][j] = 1;
                ret = ret || dfs(board, boardSize, boardColSize, word + 1, i, j, map);
                map[i][j] = 0;
            }
        }
    }
    return ret;
}

评论