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 ch = 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] == '.') continue;
            if (dfs(board, word, a, b, start + 1)) return true;
            // if (a >= 0 && a < m && b >= 0 && b < n && board[a][b] != '.') {
            //     if (dfs(board, word, a, b, u + 1)) return true;
            // }
        }
        board[x][y] = ch;
        
        return false;
    }

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

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

    bool result = solution.exist(board, word);
    cout << "Does the word " << word << " exist in the board? " << (result ? "Yes" : "No") << endl;
    
    return 0;
}

Golang 代码

// 79. 单词搜索

package main

import (
	"fmt"
)

/*
   深度优先搜索（DFS）：
       使用 DFS 搜索单词的每个字符是否存在于网格中。
       每次找到一个匹配的字符，继续搜索下一个字符，直到找到整个单词或搜索失败。
   回溯：
       在搜索过程中，标记已访问的单元格，避免重复访问。
       如果当前路径无法找到单词，回溯并恢复状态，尝试其他路径。
   边界检查：
       在搜索过程中，检查边界条件，确保不越界。

    时间复杂度：O(m*n*3^L)
        其中 m 和 n 分别是网格的行数和列数，L 是单词的长度。
        由于不能走回头路，所以除了单词首字母外，仅有三种选择。
        在最坏情况下，每个单元格都可能作为起点进行 DFS 搜索，时间复杂度为 O(m*n*3^L)。
    空间复杂度：O(m*n+L)
        visited 矩阵的空间复杂度为 O(mn)。
        DFS 的递归调用栈的深度为 O(L)。
        因此，总空间复杂度为 O(m*n+L)。
*/
// exist 判断单词是否存在于二维网格中
func exist(board [][]byte, word string) bool {
	if len(board) == 0 {
		return false
	}

	rows, cols := len(board), len(board[0])
	visited := make([][]bool, rows)
	for i := range visited {
		visited[i] = make([]bool, cols)
	}

	// 深度优先搜索
	var dfs func(r, c, index int) bool
	dfs = func(r, c, index int) bool {
		// 如果索引超出单词长度，说明找到了单词
		if index == len(word) {
			return true
		}

		// 边界检查
		if r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != word[index] {
			return false
		}

		// 标记当前节点为已访问
        // 标记已访问（原地修改字符）
        temp := board[r][c]
        board[r][c] = '#'

		// 搜索上下左右四个方向
		found := dfs(r+1, c, index+1)         // 向下搜索
		found = found || dfs(r-1, c, index+1) // 向上搜索
		found = found || dfs(r, c+1, index+1) // 向右搜索
		found = found || dfs(r, c-1, index+1) // 向左搜索

		// 回溯，恢复状态
	    board[r][c] = temp

		return found
	}

	// 遍历整个网格，寻找单词的起点
	for r := 0; r < rows; r ++ {
		for c := 0; c < cols; c ++ {
			if dfs(r, c, 0) {
				return true
			}
		}
	}

	return false
}

func main() {
	// 测试用例
	testCases := []struct {
		board    [][]byte
		word     string
		expected bool
	}{
		{
			board: [][]byte{
				{'A', 'B', 'C', 'E'},
				{'S', 'F', 'C', 'S'},
				{'A', 'D', 'E', 'E'},
			},
			word:     "ABCCED",
			expected: true,
		},
		{
			board: [][]byte{
				{'A', 'B', 'C', 'E'},
				{'S', 'F', 'C', 'S'},
				{'A', 'D', 'E', 'E'},
			},
			word:     "SEE",
			expected: true,
		},
		{
			board: [][]byte{
				{'A', 'B', 'C', 'E'},
				{'S', 'F', 'C', 'S'},
				{'A', 'D', 'E', 'E'},
			},
			word:     "ABCB",
			expected: false,
		},
	}

for i, tc := range testCases {
		fmt.Printf("Test Case %d, Input: board = [\n", i+1)
        for _, row := range tc.board {
			fmt.Printf("%v\n", row)
		}
        fmt.Printf("], word = %s\n", tc.word)
		result := exist(tc.board, tc.word)

		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, result, tc.expected)
		}
	}
}