单词搜索

https://www.lintcode.com/problem/123/?utm_source=sc-libao-ql

描述

给出一个二维的字母板和一个字符串单词，寻找字母板网格中是否存在这个字符串单词。

字符串单词可以由按顺序的相邻单元的字母组成，其中相邻单元指的是水平或者垂直方向相邻。

每个单元中的字母最多只能使用一次。

字母矩阵的维度均不超过100，字符串长度不超过100。

样例

样例 1：

输入：

board = ["ABCE","SFCS","ADEE"]word = "ABCCED"

输出：

true

解释：

[

A B C E

S F C S

A D E E

]

(0,0)->(0,1)->(0,2)->(1,2)->(2,2)->(2,1)

样例 2：

输入：

board = ["z"]word = "z"

输出：

true

解释：

[ z ]

(0,0)

分析：

用回溯backtracking, 区别dfs和backtrack和dp with memo:

回溯有剪枝，放弃无效路径立刻回溯，是特殊的dfs。普通dfs会遍历所有的可能性。而回溯通常只有一个Unique path

dp带memo是有大量重复子问题，需要保存，占内存。

本体有剪枝，重复子问题少，减枝，无需保存子状态。

注意需要记录已经visited过的点，这里直接每次递归前替换来处的点，而不是创建整个m*n数组来记载visited.

from typing import (
    List,
)
from functools import lru_cache
class Solution:
    """
    @param board: A list of lists of character
    @param word: A string
    @return: A boolean
    """
    def exist(self, board: List[List[str]], word: str) -> bool:
        # write your code here
        #dp[m][n] = dp[m-1][n] or dp[m][n-1]
        if not word:
            return True
        if not board:
            return False
        directions= {(0,1),(0,-1),(1,0),(-1,0)}
        n,m = len(board),len(board[0])
     
        def helper(x:int, y:int, i:int) -> bool:           
            if i == len(word):
                return True
            if not (0<=x< n and 0<=y<m) or word[i] != board[x][y]:
                return False

            temp = board[x][y]
            board[x][y] = '#'
            for dx,dy in directions:
                nx,ny = x+dx, y+dy
                if helper(nx,ny,i+1):
                    return True 

            board[x][y] = temp
            return False


        for i in range(n):
            for j in range(m):
                if board[i][j] == word[0] and helper(i,j,0):
                    return True
        return False