单词搜索

Leetcode Link: 79. 单词搜索 - 力扣（LeetCode） 79. 单词搜索 - 力扣（LeetCode）

题目

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

解法一

思路：回溯，自己写的有点冗长

本题的重点有两个

1. 怎么剪枝
   • 只要当前的搜索结果和word的前几个字母不匹配，就直接返回False
2. 怎么不重复利用一个位置
   • 用一个set()来保存所有走过的位置，并在回溯的过程中一直维护这个set()

题解：

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        res = []
        path = set()
        def process(i, j):
            if "".join(res) == word:
                return True
	        # 剪枝
            if "".join(res) != word[0:len(res)]:
                return False
            
            if (i-1, j) not in path and i-1>=0:
                path.add((i-1, j))
                res.append(board[i-1][j])
                if process(i-1, j):
                    return True
                res.pop()
                path.remove((i-1, j))
            if (i+1, j) not in path and i+1<=len(board)-1:
                path.add((i+1, j))
                res.append(board[i+1][j])
                if process(i+1, j):
                    return True
                res.pop()
                path.remove((i+1, j))
            if (i, j+1) not in path and j+1<=len(board[0])-1:
                path.add((i, j+1))
                res.append(board[i][j+1])
                if process(i, j+1):
                    return True
                res.pop()
                path.remove((i, j+1))
            if (i, j-1) not in path and j-1>=0:
                path.add((i, j-1))
                res.append(board[i][j-1])
                if process(i, j-1):
                    return True
                res.pop()
                path.remove((i, j-1))
            
            return False
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                path.add((i,j))
                res.append(board[i][j])
                if process(i, j):
                    return True
                res.pop()
                path.remove((i,j))
        return False
            
 

这样写的代码有两个缺点

1. 决定入口的时候需要在确定入口时维护一次，因为 process 函数里肯定会走，而不会考虑当前输入位
2. 代码太长，重复代码太多

代码去冗余 定义一个 direction 保存 4 个可以走的方向，然后遍历这个

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        res = []
        path = set()
        direc = [(0,1), (1,0), (-1,0), (0, -1)] # 四个方向
        def process(i, j):
            if "".join(res) == word:
                return True
            if "".join(res) != word[0:len(res)]:
                return False
            for d in direc:
                next_i = i+d[0]
                next_j = j+d[1]
                if (next_i, next_j) not in path and 0<=next_i<len(board) and 0<=next_j<len(board[0]):
                    path.add((next_i, next_j))
                    res.append(board[next_i][next_j])
                    if process(next_i, next_j):
                        return True
                    res.pop()
                    path.remove((next_i, next_j))
            
            return False
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                path.add((i,j))
                res.append(board[i][j])
                if process(i, j):
                    return True
                res.pop()
                path.remove((i,j))
        return False 

---

复习时的代码

思路大体一样，本题最重要的是一定要提前剪枝

这个代码是使用矩阵作为set来表示哪些走过了。

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        
        word = list(word)
        path = []
        mask = [[0 for _ in range(len(board[0]))] for _ in range(len(board))]
        direc = [[1,0], [-1,0], [0,1], [0,-1]]
 
        def bkt(i, j):
            if len(path) > len(word) or word[:len(path)] != path:
                return False
            if word == path:
                return True
            
            for d in direc:
                next_i = i + d[0]
                next_j = j + d[1]
                if 0 <= next_i < len(board) and 0 <= next_j < len(board[0]):
                    if mask[next_i][next_j] == 0:
                        path.append(board[next_i][next_j])
                        mask[next_i][next_j] = 1
                        if bkt(next_i, next_j):
                            return True
                        path.pop()
                        mask[next_i][next_j] = 0
            return False
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                path.append(board[i][j])
                mask[i][j] = 1
                if bkt(i, j):
                    return True
                path.pop()
                mask[i][j] = 0
        return False