单词搜索

题目要求

给定一个 m x n 的二维字符网格 board 和一个字符串 word。需要编写一个算法来判断 word 是否可以在网格中找到。在网格中寻找 word 时，可以按照字母顺序在相邻的单元格中移动来构建单词。这里的“相邻”单元格指的是上下左右四个方向与当前单元格相邻的单元格。在搜索过程中，同一个单元格中的字母不可以被重复使用。如果能够在网格中找到这样的单词路径，则返回 true；如果找不到，则返回 false。

解题思路

解决这个问题的一种方法是使用回溯算法。回溯算法是一种通过试错来寻找问题解决方法的算法。如果它发现已经选择的路径不可能是正确的解决方案，它将回退到上一个步骤，然后尝试其他的路径。对于这个问题，我们可以通过以下步骤来应用回溯算法：

1. 从二维网格的每一个单元格开始，尝试寻找单词 word 的第一个字母。每次递归尝试都应该标记当前单元格的使用状态，以避免重复使用。

2. 当找到第一个字母后，从当前单元格出发，递归地在所有四个相邻的单元格中寻找单词的下一个字母。

3. 对于每个相邻的单元格，检查它是否未被访问过，并且其值是否与单词 word 的下一个字母相匹配。如果匹配，则递归地继续搜索下一个字母。

4. 如果在任何递归步骤中，单词 word 的所有字母都被成功匹配，那么单词存在于网格中，返回 true。

5. 如果当前单元格的字母与单词的相应字母不匹配，或者所有相邻单元格都已经被访问过，那么回溯到上一个单元格，撤销当前单元格的访问状态，并尝试其他路径。

6. 如果所有的单元格都被尝试过后，仍然没有找到完整的单词 word，则说明单词不存在于网格中，返回 false。

7. 遍历完所有可能的起始位置后，如果没有任何一条路径能够匹配整个单词，则最终返回 false。

这个算法的关键是要有一个有效的方法来标记已经访问过的单元格，并在回溯时取消这些标记。通常可以通过修改原网格中的内容来临时标记已访问的单元格，或者使用一个额外的同等大小的布尔网格来跟踪访问状态。

Golang 版本

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

    var backtrack func(row, col, index int) bool
    backtrack = func(row, col, index int) bool {
        // Check if we have found the word
        if index == len(word) {
            return true
        }
        // Check the boundaries and if the cell is already visited or not the right letter
        if row < 0 || row >= rows || col < 0 || col >= cols || visited[row][col] || board[row][col] != word[index] {
            return false
        }
        // Mark this cell as visited
        visited[row][col] = true
        // Explore all possible directions: right, left, down, up
        if backtrack(row, col+1, index+1) || backtrack(row, col-1, index+1) ||
           backtrack(row+1, col, index+1) || backtrack(row-1, col, index+1) {
            return true
        }
        // Unmark this cell as visited (backtrack)
        visited[row][col] = false
        return false
    }

    // Start from each cell
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if backtrack(i, j, 0) {
                return true
            }
        }
    }
    return false
}

这段代码定义了一个名为 exist 的函数，它接受一个字符类型的二维切片 board 和一个字符串 word 作为参数。函数首先初始化一个 visited 二维切片来跟踪哪些单元格已经被访问过。然后定义了一个名为 backtrack 的递归辅助函数，用于执行回溯搜索。backtrack 函数会检查当前路径是否已经找到了单词，是否越界，是否已经访问过，或者是否不匹配当前需要的字母。如果当前单元格有效，它会继续探索所有可能的方向。如果在任何方向上成功找到了单词，它会返回 true。如果当前路径不可行，它会回溯并尝试其他路径。最后，exist 函数遍历网格中的每个单元格，使用 backtrack 函数来寻找单词。如果在任何起点找到了单词，它会返回 true，否则在遍历完所有单元格后返回 false。

C++版本

#include <vector>
#include <string>

class Solution {
public:
    bool exist(std::vector<std::vector<char>>& board, std::string word) {
        int rows = board.size();
        int cols = board[0].size();
        std::vector<std::vector<bool>> visited(rows, std::vector<bool>(cols, false));

        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (search(board, word, 0, i, j, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

private:
    bool search(std::vector<std::vector<char>>& board, const std::string& word, int index, int row, int col, std::vector<std::vector<bool>>& visited) {
        if (index == word.size()) return true;
        if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size()) return false;
        if (visited[row][col] || board[row][col] != word[index]) return false;

        visited[row][col] = true;
        bool found = search(board, word, index + 1, row + 1, col, visited) ||
                     search(board, word, index + 1, row - 1, col, visited) ||
                     search(board, word, index + 1, row, col + 1, visited) ||
                     search(board, word, index + 1, row, col - 1, visited);
        visited[row][col] = false;

        return found;
    }
};

这段 C++代码定义了一个名为 Solution 的类，其中包含了解决问题的 exist 方法。这个方法接受一个字符类型的二维向量 board 和一个字符串 word 作为参数。它使用一个名为 visited 的二维布尔向量来跟踪哪些单元格已经被访问过。

exist 方法遍历网格中的每个单元格，并对每个单元格调用私有辅助方法 search。search 方法是一个递归函数，它检查当前单元格是否是单词的一部分，并尝试在所有四个方向上继续搜索单词的下一个字符。如果找到了单词，search 方法会返回 true，否则在尝试了所有可能的路径后返回 false。

如果在网格中的任何位置都找不到单词，exist 方法最终返回 false。如果找到了单词，它会在第一次找到时立即返回 true。

Python 版本

class Solution:
    def exist(self, board, word):
        rows, cols = len(board), len(board[0])
        visited = [[False] * cols for _ in range(rows)]

        def backtrack(row, col, index):
            if index == len(word):
                return True
            if row < 0 or row == rows or col < 0 or col == cols or visited[row][col] or board[row][col] != word[index]:
                return False
            visited[row][col] = True
            # Explore in all directions: right, left, down, up
            if (backtrack(row, col + 1, index + 1) or
                backtrack(row, col - 1, index + 1) or
                backtrack(row + 1, col, index + 1) or
                backtrack(row - 1, col, index + 1)):
                return True
            visited[row][col] = False  # Unmark this cell for backtracking
            return False

        for i in range(rows):
            for j in range(cols):
                if backtrack(i, j, 0):  # Start the search from (i, j)
                    return True
        return False

这段 Python 代码定义了一个名为 Solution 的类，其中包含了解决问题的 exist 方法。这个方法接受一个字符类型的二维列表 board 和一个字符串 word 作为参数。它使用一个名为 visited 的二维列表来跟踪哪些单元格已经被访问过。

exist 方法遍历网格中的每个单元格，并对每个单元格调用一个名为 backtrack 的辅助函数。backtrack 是一个递归函数，它检查当前单元格是否是单词的一部分，并尝试在所有四个方向上继续搜索单词的下一个字符。如果找到了单词，backtrack 函数会返回 True，否则在尝试了所有可能的路径后返回 False。

如果在网格中的任何位置都找不到单词，exist 方法最终返回 False。如果找到了单词，它会在第一次找到时立即返回 True。

Java 版本

public class Solution {
    public boolean exist(char[][] board, String word) {
        int rows = board.length;
        int cols = board[0].length;
        boolean[][] visited = new boolean[rows][cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (search(board, word, i, j, 0, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean search(char[][] board, String word, int row, int col, int index, boolean[][] visited) {
        if (index == word.length()) {
            return true;
        }
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length) {
            return false;
        }
        if (visited[row][col] || board[row][col] != word.charAt(index)) {
            return false;
        }
        visited[row][col] = true;
        if (search(board, word, row - 1, col, index + 1, visited) ||
            search(board, word, row + 1, col, index + 1, visited) ||
            search(board, word, row, col - 1, index + 1, visited) ||
            search(board, word, row, col + 1, index + 1, visited)) {
            return true;
        }
        visited[row][col] = false; // backtrack
        return false;
    }
}

这段 Java 代码定义了一个名为 Solution 的类，其中包含了解决问题的 exist 方法。这个方法接受一个字符类型的二维数组 board 和一个字符串 word 作为参数。它使用一个名为 visited 的二维布尔数组来跟踪哪些单元格已经被访问过。

exist 方法遍历网格中的每个单元格，并对每个单元格调用一个名为 search 的私有辅助方法。search 是一个递归函数，它检查当前单元格是否是单词的一部分，并尝试在所有四个方向上继续搜索单词的下一个字符。如果找到了单词，search 方法会返回 true，否则在尝试了所有可能的路径后返回 false。

如果在网格中的任何位置都找不到单词，exist 方法最终返回 false。如果找到了单词，它会在第一次找到时立即返回 true。在回溯过程中，visited 数组的相应位置会被重置，以便可以重新使用该单元格。

Rust 版本

#![allow(unused)]
fn main() {
impl Solution {
    pub fn exist(board: Vec<Vec<char>>, word: String) -> bool {
        let rows = board.len();
        let cols = board[0].len();
        let word_chars: Vec<char> = word.chars().collect();
        let mut visited = vec![vec![false; cols]; rows];

        for i in 0..rows {
            for j in 0..cols {
                if Self::dfs(&board, &word_chars, i, j, 0, &mut visited) {
                    return true;
                }
            }
        }

        false
    }

    fn dfs(board: &Vec<Vec<char>>, word: &Vec<char>, row: usize, col: usize, index: usize, visited: &mut Vec<Vec<bool>>) -> bool {
        if index == word.len() {
            return true;
        }
        if row >= board.len() || col >= board[0].len() || visited[row][col] || board[row][col] != word[index] {
            return false;
        }

        visited[row][col] = true;

        let row_offsets = [1, 0, -1, 0];
        let col_offsets = [0, 1, 0, -1];

        for k in 0..4 {
            let new_row = row as i32 + row_offsets[k];
            let new_col = col as i32 + col_offsets[k];
            if new_row >= 0 && new_col >= 0 && Self::dfs(board, word, new_row as usize, new_col as usize, index + 1, visited) {
                return true;
            }
        }

        visited[row][col] = false;
        false
    }
}
}

这段 Rust 代码定义了一个名为 Solution 的结构体，其中包含了解决问题的 exist 方法。这个方法接受一个字符类型的二维向量 board 和一个字符串 word 作为参数，并返回一个布尔值。它使用一个名为 visited 的二维向量来跟踪哪些单元格已经被访问过。

exist 方法遍历网格中的每个单元格，并对每个单元格调用一个名为 dfs 的私有辅助方法。dfs 是一个递归函数，它检查当前单元格是否是单词的一部分，并尝试在所有四个方向上继续搜索单词的下一个字符。如果找到了单词，dfs 方法会返回 true，否则在尝试了所有可能的路径后返回 false。

如果在网格中的任何位置都找不到单词，exist 方法最终返回 false。如果找到了单词，它会在第一次找到时立即返回 true。在回溯过程中，visited 向量的相应位置会被重置，以便可以重新使用该单元格。

请注意，Rust 中的索引必须是非负数，因此在处理行和列的偏移时，我们需要将它们从 i32 转换为 usize，同时确保它们不会变成负数。

总结

上面的 Rust 代码实现了一个经典的回溯算法，用于在一个给定的字符网格中搜索一个指定的单词。这个算法的核心是深度优先搜索（DFS），它尝试从网格中的每个位置开始，探索所有可能的路径以找到单词。以下是解法的关键点：

1. 二维访问数组：使用一个二维布尔数组 visited 来跟踪每个单元格是否已经被访问过，以防止重复访问。

2. 递归 DFS 函数：dfs 函数是一个递归函数，它接受当前位置、单词、当前索引和访问数组作为参数。它会检查当前位置是否可以作为单词的一部分，并递归地在四个方向（上、下、左、右）探索下一个字符。

3. 边界和匹配条件检查：在每次递归调用中，都会检查当前位置是否越界，当前字符是否与单词中相应位置的字符匹配，以及该位置是否已经被访问过。

4. 回溯：在探索完一个位置的所有可能方向后，如果没有找到正确的路径，算法会回溯，即撤销当前位置的访问状态，然后返回到上一个位置继续搜索。

5. 成功条件：如果当前索引达到了单词的长度，意味着单词已经被完全找到，函数返回 true。

6. 循环启动 DFS：在 exist 函数中，通过双层循环遍历网格中的每个单元格，并从每个单元格启动 DFS 搜索。如果任何一个单元格的 DFS 返回 true，则整个函数返回 true。

7. 返回结果：如果在整个网格中都没有找到单词，则函数最终返回 false。

这种解法在解决二维网格搜索问题时非常有效，尤其是在需要验证多个可能性并且每个选择都依赖于前一个选择的情况下。回溯算法通过尝试所有可能的解决方案来找到问题的答案，如果当前尝试失败了，它会撤销最后的选择并尝试另一种可能的路径。