79.单词搜索

回溯，https://leetcode.cn/problems/word-search/

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

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

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

提示：

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

思路：

用dfs像周围四个方向搜索下一个字母
剪枝1：如果最后一个字母出现的频率比第一个字母低，就反过来搜索，效率更高
剪枝2：如果一个字母在单词中出现的次数大于在表中出现的次数，直接return false

3535ms，击败58.21%

python

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]:
                return False
            if k == len(word) - 1:
                return True
            tmp, board[i][j] = board[i][j], '/'
            res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
            board[i][j] = tmp
            return res

        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0):
                    return True
        return False

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

To optimize the solution using search pruning, we can add a few checks to avoid unnecessary recursive calls. One effective technique is to use a set to keep track of visited cells, which helps in avoiding revisiting the same cell within the same path.

Here is the optimized Python code:

5133ms，击败18.36%

python

from typing import List

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k, visited):
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k] or (i, j) in visited:
                return False
            if k == len(word) - 1:
                return True
            visited.add((i, j))
            res = (dfs(i + 1, j, k + 1, visited) or
                   dfs(i - 1, j, k + 1, visited) or
                   dfs(i, j + 1, k + 1, visited) or
                   dfs(i, j - 1, k + 1, visited))
            visited.remove((i, j))
            return res

        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0, set()):
                    return True
        return False

Explanation:

Visited Set: A set visited is used to keep track of the cells that have been visited in the current path.
DFS Function: The dfs function now takes an additional parameter visited to manage the visited cells.
Pruning: Before making recursive calls, the function checks if the current cell is already visited or if it does not match the current character in the word.
Backtracking: After exploring all possible paths from the current cell, the cell is removed from the visited set to allow other paths to use it.

【汤伟杰，24信息管理系】思路：

遍历棋盘的每一个位置，如果是单词的第一个字母就进入dfs的搜索，在dfs中设置一个idx索引来跟踪word的字母，之后就是很正常的搜索了。这道题能学到的东西是题解里面的两个优化：

一是统计棋盘所有字母的个数，如果其中出现在word中字母的个数少于word中需求的字母数量，那么可以直接返回False；二是统计棋盘中的单词首字母和尾字母的个数，从个数少的一端进行dfs。

这道题由于只需要返回“能不能找到单词”，因此设置的dfs的返回值是布尔值，那么在每次调用函数本身的时候可以写成if dfs(word, s, nx, ny, visited, idx): return True，这样的好处是：如果dfs到了单词末尾，那么会进入if语句的return True，从而逐层返回True，就不会进行visited的状态恢复了。很方便，这个写法也很巧妙。

python

class Solution:
    def exist(self, s: List[List[str]], word: str) -> bool:
        cnt = Counter(c for row in s for c in row)
        if not cnt >= Counter(word):  # 优化一
            return False
        if cnt[word[-1]] < cnt[word[0]]:  # 优化二
            word = word[::-1]
            
        n,m=len(s),len(s[0])
        dx,dy=[0,-1,1,0],[-1,0,0,1]
        def dfs(word,s,x,y,visited,idx):
            idx+=1
            if idx==len(word):
                return True
            for i in range(4):
                nx,ny=x+dx[i],y+dy[i]
                if 0<=nx<n and 0<=ny<m and word[idx]==s[nx][ny] and (nx,ny) not in visited:
                    visited.add((nx,ny))
                    if dfs(word,s,nx,ny,visited,idx):
                        return True
                    visited.remove((nx,ny))
            return False

        def search(word,s):
            for i in range(n):
                for j in range(m):
                    if s[i][j]==word[0]:
                        if dfs(word,s,i,j,{(i,j)},0):
                            return True
            return False

        return search(word,s)

79.单词搜索 ​

79.单词搜索