python 练习题- 取字母

 1 # @Author  :whyCai
 2 # @Time    :2021/3/18 21:53
 3 
 4 """
 5 二维网格和一个单词，找出该单词是否存在网格中
 6 1.单词必须按照字母顺序，通过相邻的单元格内的字母工程，其中 “相邻”单元格是那些水平或垂直相邻的单元格，同一个单元格内的字母不允许重复使用
 7 
 8 例子：
 9 board = 
10 [
11 ['A','B','C','E'],
12 ['S','F','C','S'],
13 ['A','D','E','E']
14 ]
15 
16 word = 'ABCCED' 返回true
17 word = 'SEE' 返回true
18 word = 'ABCB' 返回false
19 
20 board和word只包含大小写英文字母
21 board、board[i],word 长度 >=1
22 """
23 import copy
24 
25 class Solution:
26     def wordExist(self, board,word) -> bool:
27         #网格 长、高，单词的长度
28         boardLen = len(board[0])
29         boardHei = len(board)
30         wordLen = len(word)
31 
32         #单词长度比网格还多
33         if wordLen > boardLen * boardHei:return False
34 
35         def wordCont(i, j, pos,w):
36             '''
37             判断网格周围是否存在该单词
38             :param i: 网格 横坐标
39             :param j: 网格纵坐标
40             :param pos: 标识网格，其中的值为'1'，代表已使用
41             :param w: 单词的下标
42             :return: 
43             '''
44             # 标识该位置已使用
45             pos[i][j] = '1'
46             #长度相同，单词遍历结束
47             if  wordLen ==w:return True
48 
49             # 从已找到的网格坐标（i,j）的四周查找下个单词是否存在
50             for a, b in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
51                 ia = i + a
52                 jb = j + b
53                 if ia >= 0 and ia < boardHei and jb >= 0 and jb < boardLen and pos[ia][jb] != '1' and board[ia][jb] == word[w]:
54                     if wordCont(ia,jb,pos,w+1) :return True
55                     #标识恢复初始原值，重新查询
56                     pos=copy.deepcopy(board)
57                     pos[i][j] = '1'
58             return False
59 
60         #遍历网格，如果第一个单词存在，则进入 wordCont()查询剩余单词
61         for i in range(boardHei):
62             for j in range(boardLen):
63                 if board[i][j] == word[0] and wordCont(i,j,copy.deepcopy(board),1):
64                     return True
65         return False
66 
67 print(Solution().wordExist([['A','B','C','E'],['S','F','C','S'],['A','D','E','E']],'ABCCED'))