[Leetcode]79. Word Search(C++)

题目描述

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

例子

例子 1

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true

例子 2

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" Output: true

例子 3

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" Output: false

Follow Up

Could you use search pruning to make your solution faster with a larger board?

Constraints

m == board.length

n = board[i].length

1 <= m, n <= 6

1 <= word.length <= 15

board and word consists of only lowercase and uppercase English letters.

解题思路

这道题要求在矩阵通过上下左右寻找一个单词，每个位置的字母只能用一次。看数据规模不大所以思路可以是用回溯来进行暴力递归搜索。具体的方法是在每个位置首先判断该位置元素是否符合当前寻找的字符，接下来标志该位置为已使用，在四个方向进行深度优先搜索进行递归求解，直至：

到达目标单词末尾，返回 true
中间任何一个位置，如果索引位置越界、当前位置已经被使用过、当前位置字母不是要目标字母，返回 false

四个方向遍历后，如果其中一个方向返回 true 则已求解成功直接返回 true，否则复位当前位置为未使用，进行下一个位置的搜索。

代码如下：

#include <string>
#include <vector>

class Solution {
public:
    bool exist(std::vector<std::vector<char>>& board, std::string word) {
        directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        is_used = std::vector<std::vector<bool>>(
            board.size(), std::vector<bool>(board[0].size(), false));
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[0].size(); ++j) {
                if (dfs(board, i, j, word, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

private:
    std::vector<std::pair<int, int>> directions;
    std::vector<std::vector<bool>> is_used;

    bool dfs(const std::vector<std::vector<char>>& board, int row, int col,
             const std::string& word, int index) {
        if (index == word.size()) {
            return true;
        }

        if (row >= board.size() || row < 0 || col >= board[0].size() ||
            col < 0 || is_used[row][col] || board[row][col] != word[index]) {
            return false;
        }

        is_used[row][col] = true;

        for (int i = 0; i < 4; i++) {
            if (dfs(board, row + directions[i].first,
                    col + directions[i].second, word, index + 1)) {
                return true;
            }
        }

        is_used[row][col] = false;

        return false;
    }
};

时间复杂度: O(2^mn)
空间复杂度: O(mn)

GitHub 代码同步地址： 79.WordSearch.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions