题目标题

给个一个二维矩阵,矩阵中每一位是字符,从任意一个字符出发,不断向上下左右能拼成一个字符串;给定一些字符串,逐个判断是否能在该矩阵中拼出

难度:初级

数据分析
参考解析

class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
row, col = len(board), len(board[0])
visit = [[0] * col for i in range(row)]

  1. def dfs(x: int, y: int, u: int):
  2. if u == len(word):
  3. return True
  4. visit[x][y] = 1
  5. dx = [-1,0,1,0]
  6. dy = [0,1,0,-1]
  7. for i in range(4):
  8. a,b = x + dx[i], y + dy[i]
  9. if 0<=a<row and 0<=b<col and 1-visit[a][b] and board[a][b] == word[u]:
  10. if dfs(a,b,u+1):
  11. return True
  12. #end_for
  13. visit[x][y] = 0
  14. return False
  15. for i in range(row):
  16. for j in range(col):
  17. if board[i][j] == word[0]:
  18. if dfs(i, j, 1):
  19. return True
  20. #end_for
  21. return False