[Python知识库]LeetCode - 解题笔记 - 79 - Word Search

Solution 1

一开始我以为这道题是BFS，但是在套模板的时候发现了一个变化：遍历过程中需要根据考察的具体字符重新判定是否遍历过（某个位置在考察第三个字符时遍历过，那么在考察第七个字符时还是可以遍历的），因此还是写成DFS的形式了。

• 时间复杂度：$O(MN\times 3^L)$，其中$M$和$N$时输入地图的高度和宽度，$L$为字符串长度，搜索树的分支数最多为3（因为四个方向，最坏走3次）
• 空间复杂度：$O(MN)$，每个遍历位置的状态保存

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size()));
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[0].size(); ++j) {
                if (board[i][j] == word.at(0) && this->dfs(board, visited, i, j, word, 0)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
private:
    vector<pair<int, int>> dirs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    bool dfs(vector<vector<char>> & board, vector<vector<bool>> & visited, int i, int j, string & word, int pos) {
        bool result = false;
        if (board[i][j] != word.at(pos)) { return false; }
        if (pos == word.size() - 1) { return true; }
        
        visited[i][j] = true;
        
        for (auto & dir: dirs) {
            int iNext = i + dir.first, jNext = j + dir.second;
            if (
                iNext >= 0 && iNext < board.size() &&
                jNext >= 0 && jNext < board[0].size() && 
                !visited[iNext][jNext]
               ) {
                if (this->dfs(board, visited, iNext, jNext, word, pos + 1)) { result = true; break; }
            }
        }
        
        visited[i][j] = false;
        
        return result;
    }
};

Solution 2

Solution 1的Python实现，不知道为啥我的实现特别慢

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        visited = [[False] * len(board[0]) for i in range(len(board))]
        
        def dfs(i: int, j: int, pos: int) -> bool:
            result = False
            if board[i][j] != word[pos]: return False
            if pos == len(word) - 1: return True
            
            visited[i][j] = True
            # print(i, j, board[i][j], pos, word[pos])
            for ioffset, joffset in dirs:
                iNext, jNext = i + ioffset, j + joffset
                if 0 <= iNext < len(board) and 0 <= jNext < len(board[0]) and not visited[iNext][jNext]:
                    # print("\t", iNext, jNext, board[iNext][jNext], pos + 1, word[pos + 1])
                    if dfs(iNext, jNext, pos + 1):
                        result = True
                        break
            
            visited[i][j] = False
            return result
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                if  board[i][j] == word[0] and dfs(i, j, 0):
                    return True
        
        return False