leetcode79：单词搜索

题目链接

leetcode

题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。
如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

C++ 代码

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

/*
    回溯法，深度优先搜索

    深度优先搜索中，最重要的是考虑搜索顺序。
    先枚举单词的起点，然后枚举单词的每个字母。
    这个过程中将已经使用过的字母标记，避免重复使用字符。

    时间复杂度：O(m*n*3^k)
        其中 m, n 为网格的长度与宽度，m 是字符串的个数，n 是字符串的长度。
        单词起点一共有 m*n 个，单词的每个字母可以选择上下左右四个方向，
        由于不能走回头路，所以除了单词首字母外，仅有三种选择。
        时间复杂度是 O(m*n*3^k)。
    空间复杂度：O(n^2)
        存储动态规划数组。
        在最坏的情况下，递归的深度可以达到 n，空间复杂度为 O(n)。
*/
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        m = board.size(), n = board[0].size();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }

        return false;
    }

    bool dfs(vector<vector<char>>& board, string& word, int x, int y, int start) {
        // 边界条件：字符不匹配
        if (board[x][y] != word[start]) {
            return false;
        }
        // 结束条件：找到整个单词
        if (start == word.size()-1) {
            return true;
        }

        char c = board[x][y];
        board[x][y] = '.';
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < m && b >= 0 && b < n && board[a][b] != '.') {
                if (dfs(board, word, a, b, start + 1)) {
                    return true;
                }
            }
        }
        board[x][y] = c;
        
        return false;
    }

private:
    int m, n;
    int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
};

// 辅助函数：打印二维数组
void printArray(const vector<vector<char>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << "\"" <<nums[i][j] << "\"";
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    Solution solution;
    vector<vector<vector<char>>> board_cases = {
        {
            {'A','B','C','E'},
            {'S','F','C','S'},
            {'A','D','E','E'}
        },
        {
            {'A','B','C','E'},
            {'S','F','C','S'},
            {'A','D','E','E'}
        },
        {
            {'A','B','C','E'},
            {'S','F','C','S'},
            {'A','D','E','E'}
        }
    };
    vector<string> word_cases = {
        "ABCCED",
        "SEE",
        "ABCB"
    };

    for (size_t i = 0; i < board_cases.size(); i++) {
        auto& board = board_cases[i];
        string word = word_cases[i];

        cout << "Input: board = ";
        printArray(board);
        cout << ", word = " << word << endl;

        bool result = solution.exist(board, word);
        cout << "Output: " << (result ? "true" : "false") << endl;
    }

    return 0;
}