问题描述

字母迷宫游戏初始界面记作 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 = Falsedef 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 = Truereturnfor i in range(row):for j in range(column):if grid[i][j] != target[0]:continuewalk(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 spamspam = "nonlocal spam"def do_global():global spamspam = "global spam"spam = "test spam"do_local()# do_local()中的spam是函数do_local内的局部变量，修改以后无法影响到外层，因此输出  test spamprint("After local assignment:", spam)do_nonlocal()# do_nonlocal()中的spam用nonlocal修饰，相当于对do_nonlocal()外一层函数scope_test()中的spam进行修改# 因此输出 nonlocal spamprint("After nonlocal assignment:", spam)do_global()# do_global()中的spam用global修饰，相当于对最外层中的spam进行修改# 输出语句仍位于scope_test()，因此输出 nonlocal spamprint("After global assignment:", spam)scope_test()
# do_global()中的spam用global修饰，因此最外层有全局变量spam=‘global spam’
print("In global scope:", spam)

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

self.实例变量