网盘建网站,中国铁工建设有限公司网站,找建筑工作哪个网站好,泸县建设局网站Python算法题集_单词搜索 题22#xff1a;单词搜索1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【原始矩阵状态回溯】2) 改进版一【字典检测原始矩阵状态回溯】3) 改进版二【矩阵状态回溯】 4. 最优算法5. 相关资源 本文为Python算法题集之一… Python算法题集_单词搜索 题22单词搜索1. 示例说明2. 题目解析- 题意分解- 优化思路- 测量工具 3. 代码展开1) 标准求解【原始矩阵状态回溯】2) 改进版一【字典检测原始矩阵状态回溯】3) 改进版二【矩阵状态回溯】 4. 最优算法5. 相关资源 本文为Python算法题集之一的代码示例
题22单词搜索
1. 示例说明 给定一个 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.lengthn board[i].length1 m, n 61 word.length 15board 和 word 仅由大小写英文字母组成 **进阶**你可以使用搜索剪枝的技术来优化解决方案使其在 board 更大的情况下可以更快解决问题 2. 题目解析
- 题意分解
本题是在矩阵内检查是否有相邻元素组成对应单词矩阵内每一个元素最多有4个方向考虑到搜索进入方向从第二个字母开始最多有3个方向可以用回溯法解题回溯法探索与回溯法是一种选优搜索法又称为试探法按选优条件向前搜索以达到目标。但当探索到某一步时发现原先选择并不优或达不到目标就退回一步重新选择这种走不通就退回再走的技术为回溯法。
- 优化思路 通常优化减少循环层次 通常优化增加分支减少计算集 通常优化采用内置算法来提升计算速度 分析题目特点分析最优解 可以使用字典进行字符检测只有存在检测单词所有字符的矩阵才展开搜索 可以使用原始矩阵保存检测状态也可以另外使用矩阵保存检测状态 - 测量工具
本地化测试说明LeetCode网站测试运行时数据波动很大【可把页面视为功能测试】因此需要本地化测试解决数据波动问题CheckFuncPerf本地化函数用时和内存占用测试模块已上传到CSDN地址Python算法题集_检测函数用时和内存占用的模块本题本地化超时测试用例自己生成详见章节【最优算法】代码文件包含在【相关资源】中 3. 代码展开
1) 标准求解【原始矩阵状态回溯】
使用原始矩阵保存检测状态【当前已检测路径值设置为’】实现回溯
页面功能测试马马虎虎超过76%
import CheckFuncPerf as cfpclass 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 Falseif icheckpos len(word) - 1:return Trueboard[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 resultfor 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 Truereturn FalseaSolution Solution()
checkmapmatrix copy.deepcopy(mapmatrix)
result cfp.getTimeMemoryStr(aSolution.exist_base, checkmapmatrix, checkword)
print(result[msg], 执行结果 {}.format(result[result]))# 运行结果
函数 exist_base 的运行时间为 24.00 ms内存使用量为 684.00 KB 执行结果 True2) 改进版一【字典检测原始矩阵状态回溯】
使用字典进行字符集检测符合要求的才开始回溯回溯中使用原始矩阵保存检测状态
页面功能测试性能卓越超越95%
import CheckFuncPerf as cfpclass Solution:def exist_ext1(self, board, word):def preCheck():preDict {}for chr in word:if chr in preDict:preDict[chr] 1else:preDict[chr] 1for arow in board:for achr in arow:if achr in preDict and preDict[achr] 0:preDict[achr] - 1for aval in preDict.values():if aval 0:return Falsereturn Truedef dfs_backtrack(irow, icol, icheckpos):if icheckpos imaxlen:return Trueif 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 Trueboard[irow][icol] word[icheckpos]return Falseif preCheck() False:return Falseimaxrow, 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 Truereturn FalseaSolution Solution()
checkmapmatrix copy.deepcopy(mapmatrix)
result cfp.getTimeMemoryStr(aSolution.exist_ext1, checkmapmatrix, checkword)
print(result[msg], 执行结果 {}.format(result[result]))# 运行结果
函数 exist_ext1 的运行时间为 25.01 ms内存使用量为 644.00 KB 执行结果 True3) 改进版二【矩阵状态回溯】
使用多维列表结构保存检测路径状态实现回溯
页面功能测试性能良好超过88%
import CheckFuncPerf as cfpclass Solution:def exist_ext2(self, board, word):imaxrow, imaxcol, imaxlen len(board), len(board[0]), len(word)path [] * imaxlenmap_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 Falseif checkmatrix[irow][icol]:return Falseif board[irow][icol] ! word[icheckpos]:return Falseif icheckpos imaxlen - 1:return Truepath[icheckpos] word[icheckpos]checkmatrix[irow][icol] Trueif 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 Truecheckmatrix[irow][icol] Falsepath[icheckpos] return Falsefor irow in range(imaxrow):for icol in range(imaxcol):if dfs_backtrack(0, irow, icol, imaxrow, imaxcol, board, word, map_check):return Truereturn FalseaSolution Solution()
checkmapmatrix copy.deepcopy(mapmatrix)
result cfp.getTimeMemoryStr(aSolution.exist_ext2, checkmapmatrix, checkword)
print(result[msg], 执行结果 {}.format(result[result]))# 运行结果
函数 exist_ext2 的运行时间为 43.01 ms内存使用量为 384.00 KB 执行结果 True4. 最优算法
根据本地日志分析最优算法为第1种方式【原始矩阵状态回溯】exist_base
本题测试数据似乎能推出以下结论
字典过滤检测性能消耗极小额外的数据存储带来额外的性能消耗在检测集合和字符串多样化的情况下第二种算法其实是会表现更好
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]))# 算法本地速度实测比较
函数 exist_base 的运行时间为 24.00 ms内存使用量为 684.00 KB 执行结果 True
函数 exist_ext1 的运行时间为 25.01 ms内存使用量为 644.00 KB 执行结果 True
函数 exist_ext2 的运行时间为 43.01 ms内存使用量为 384.00 KB 执行结果 True5. 相关资源
本文代码已上传到CSDN地址Python算法题源代码_LeetCode(力扣)_单词搜索
一日练一日功一日不练十日空
may the odds be ever in your favor ~
