问题描述

字母迷宫游戏初始界面记作 m x n 二维字符串数组 grid，请判断玩家是否能在 grid 中找到目标单词 target。
注意：寻找单词时 必须 按照字母顺序，通过水平或垂直方向相邻的单元格内的字母构成，同时，同一个单元格内的字母 不允许被重复使用 。

题解

注：该方法时间复杂度较高

class Solution:

    def wordPuzzle(self, grid: List[List[str]], target: str) -> bool:
        row = len(grid)
        column = len(grid[0])
        self.Flag = False

        def walk(i, j, k, pos):
            if i + 1 < row and k + 1 < len(target) and grid[i + 1][j] == target[k + 1]:
            # 向上走
                if (i + 1, j) not in pos:
                # 判断该单元格有没有走过
                    walk(i + 1, j, k + 1, pos + [(i + 1, j)])

            if i - 1 >= 0 and k + 1 < len(target) and grid[i - 1][j] == target[k + 1]:
            # 向下走
                if (i - 1, j) not in pos:
                    walk(i - 1, j, k + 1, pos + [(i - 1, j)])

            if j + 1 < column and k + 1 < len(target) and grid[i][j + 1] == target[k + 1]:
            # 向右走
                if (i, j + 1) not in pos:
                    walk(i, j + 1, k + 1, pos + [(i, j + 1)])

            if j - 1 >= 0 and k + 1 < len(target) and grid[i][j - 1] == target[k + 1]:
            # 向左走
                if (i, j - 1) not in pos:
                    walk(i, j - 1, k + 1, pos + [(i, j - 1)])

            if k == len(target) - 1:
                self.Flag = True
                return

        for i in range(row):
            for j in range(column):
                if grid[i][j] != target[0]:
                    continue
                walk(i, j, 0, [(i, j)])

        return self.Flag

踩坑记录

global和nonlocal关键字的区别：

• global申明全局变量，即最外层变量
• nonlocal申明外一层变量

def scope_test():
    def do_local():
        spam = "local spam"

    def do_nonlocal():
        nonlocal spam
        spam = "nonlocal spam"

    def do_global():
        global spam
        spam = "global spam"

    spam = "test spam"
    do_local()
    # do_local()中的spam是函数do_local内的局部变量，修改以后无法影响到外层，因此输出  test spam
    print("After local assignment:", spam)
    
    do_nonlocal()
    # do_nonlocal()中的spam用nonlocal修饰，相当于对do_nonlocal()外一层函数scope_test()中的spam进行修改
    # 因此输出 nonlocal spam
    print("After nonlocal assignment:", spam)
    
    do_global()
    # do_global()中的spam用global修饰，相当于对最外层中的spam进行修改
    # 输出语句仍位于scope_test()，因此输出 nonlocal spam
    print("After global assignment:", spam)

scope_test()
# do_global()中的spam用global修饰，因此最外层有全局变量spam=‘global spam’
print("In global scope:", spam)

类中可以用实例变量替换全局变量

self.实例变量