# -*- coding:utf-8 -*-
# Author='长孤秋落' '2024/2/27'
# 博客：https://blog.csdn.net/weixin_36928396?type=blog
# may the odds be ever in your favor
"""
79. 单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true
示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false
提示：
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成
进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
"""
import CheckFuncPerf as cfp
class Solution:
def exist_base(self, board, word):
def dfs_backtrack(irow, icol, icheckpos):
if not 0 <= irow < len(board) or not 0 <= icol < len(board[0]) or board[irow][icol] != word[icheckpos]:
return False
if icheckpos == len(word) - 1:
return True
board[irow][icol] = ''
result = dfs_backtrack(irow + 1, icol, icheckpos + 1) or dfs_backtrack(irow - 1, icol, icheckpos + 1) or \
dfs_backtrack(irow, icol + 1, icheckpos + 1) or dfs_backtrack(irow, icol - 1, icheckpos + 1)
board[irow][icol] = word[icheckpos]
return result
for irow in range(len(board)):
for icol in range(len(board[0])):
if board[irow][icol] == word[0] and dfs_backtrack(irow, icol, 0):
return True
return False
def exist_ext1(self, board, word):
def preCheck():
preDict = {}
for chr in word:
if chr in preDict:
preDict[chr] += 1
else:
preDict[chr] = 1
for arow in board:
for achr in arow:
if achr in preDict and preDict[achr] > 0:
preDict[achr] -= 1
for aval in preDict.values():
if aval > 0:
return False
return True
def dfs_backtrack(irow, icol, icheckpos):
if icheckpos == imaxlen:
return True
if 0 <= irow < imaxrow and 0 <= icol < imaxcol and board[irow][icol] == word[icheckpos]:
board[irow][icol] = ''
for inextrow, inextcol in (irow, icol + 1), (irow, icol - 1), (irow + 1, icol), (irow - 1, icol):
if dfs_backtrack(inextrow, inextcol, icheckpos + 1):
return True
board[irow][icol] = word[icheckpos]
return False
if preCheck() == False:
return False
imaxrow, imaxcol, imaxlen = len(board), len(board[0]), len(word)
for irow in range(imaxrow):
for icol in range(imaxcol):
if board[irow][icol] == word[0] and dfs_backtrack(irow, icol, 0):
return True
return False
def exist_ext2(self, board, word):
imaxrow, imaxcol, imaxlen = len(board), len(board[0]), len(word)
path = [''] * imaxlen
map_check = [[False] * imaxcol for x in range(imaxrow)]
def dfs_backtrack(icheckpos, irow, icol, imaxrow, imaxcol, board, word, checkmatrix):
if irow < 0 or irow >= imaxrow or icol < 0 or icol >= imaxcol:
return False
if checkmatrix[irow][icol]:
return False
if board[irow][icol] != word[icheckpos]:
return False
if icheckpos == imaxlen - 1:
return True
path[icheckpos] = word[icheckpos]
checkmatrix[irow][icol] = True
if dfs_backtrack(icheckpos + 1, irow - 1, icol, imaxrow, imaxcol, board, word, checkmatrix) or \
dfs_backtrack(icheckpos + 1, irow + 1, icol, imaxrow, imaxcol, board, word, checkmatrix) or \
dfs_backtrack(icheckpos + 1, irow, icol - 1, imaxrow, imaxcol, board, word, checkmatrix) or \
dfs_backtrack(icheckpos + 1, irow, icol + 1, imaxrow, imaxcol, board, word, checkmatrix):
return True
checkmatrix[irow][icol] = False
path[icheckpos] = ''
return False
for irow in range(imaxrow):
for icol in range(imaxcol):
if dfs_backtrack(0, irow, icol, imaxrow, imaxcol, board, word, map_check):
return True
return False
if __name__ == '__main__':
print('Hot60.py')
# 功能测试
# mapmatrix = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
# checkword = "ESEE"
# aSolution = Solution()
# result = cfp.getTimeMemoryStr(aSolution.exist_ext2, mapmatrix, checkword)
# print(result['msg'], '执行结果 = {}'.format(result['result']))
# 超时测试
import random, copy
imaxrow, imaxcol, checkword = 500, 300, ''
mapmatrix=[['' for x in range(imaxcol)] for y in range(imaxrow)]
words = list('abcdefghijklmnopqrstuvwxyz')
for irow in range(imaxrow):
for icol in range(imaxcol):
mapmatrix[irow][icol] = random.choice(words)
for iIdx in range(1, min(imaxrow, imaxcol)):
checkword += mapmatrix[imaxrow-iIdx][imaxcol-iIdx] + mapmatrix[imaxrow-iIdx][imaxcol-iIdx-1]
aSolution = Solution()
checkmapmatrix = copy.deepcopy(mapmatrix)
result = cfp.getTimeMemoryStr(aSolution.exist_base, checkmapmatrix, checkword)
print(result['msg'], '执行结果 = {}'.format(result['result']))
checkmapmatrix = copy.deepcopy(mapmatrix)
result = cfp.getTimeMemoryStr(aSolution.exist_ext1, checkmapmatrix, checkword)
print(result['msg'], '执行结果 = {}'.format(result['result']))
checkmapmatrix = copy.deepcopy(mapmatrix)
result = cfp.getTimeMemoryStr(aSolution.exist_ext2, checkmapmatrix, checkword)
print(result['msg'], '执行结果 = {}'.format(result['result']))
