Python算法题集_单词搜索

Python算法题集_单词搜索

  • 题22：单词搜索
  • 1. 示例说明
  • 2. 题目解析
    • - 题意分解
    • - 优化思路
    • - 测量工具
  • 3. 代码展开
    • 1) 标准求解【原始矩阵状态+回溯】
    • 2) 改进版一【字典检测+原始矩阵状态+回溯】
    • 3) 改进版二【矩阵状态+回溯】
  • 4. 最优算法
  • 5. 相关资源

本文为Python算法题集之一的代码示例

题22：单词搜索

1. 示例说明

  • 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

    单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

    示例 1：

    img

    输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

    示例 2：

    img

    输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

    示例 3：

    img

    输入：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 更大的情况下可以更快解决问题？

2. 题目解析

- 题意分解

  1. 本题是在矩阵内检查是否有相邻元素组成对应单词
  2. 矩阵内每一个元素最多有4个方向，考虑到搜索进入方向，从第二个字母开始，最多有3个方向，可以用回溯法解题
  3. 回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。

- 优化思路

  1. 通常优化：减少循环层次

  2. 通常优化：增加分支，减少计算集

  3. 通常优化：采用内置算法来提升计算速度

  4. 分析题目特点，分析最优解

    1. 可以使用字典进行字符检测，只有存在检测单词所有字符的矩阵才展开搜索

    2. 可以使用原始矩阵保存检测状态，也可以另外使用矩阵保存检测状态

- 测量工具

  • 本地化测试说明：LeetCode网站测试运行时数据波动很大【可把页面视为功能测试】，因此需要本地化测试解决数据波动问题
  • CheckFuncPerf（本地化函数用时和内存占用测试模块）已上传到CSDN，地址：Python算法题集_检测函数用时和内存占用的模块
  • 本题本地化超时测试用例自己生成，详见章节【最优算法】，代码文件包含在【相关资源】中

3. 代码展开

1) 标准求解【原始矩阵状态+回溯】

使用原始矩阵保存检测状态【当前已检测路径值设置为’'】，实现回溯

页面功能测试，马马虎虎，超过76%在这里插入图片描述

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

aSolution = 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 执行结果 = True

2) 改进版一【字典检测+原始矩阵状态+回溯】

使用字典进行字符集检测，符合要求的才开始回溯；回溯中使用原始矩阵保存检测状态

页面功能测试，性能卓越，超越95%在这里插入图片描述

import CheckFuncPerf as cfp

class Solution:
 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

aSolution = 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 执行结果 = True

3) 改进版二【矩阵状态+回溯】

使用多维列表结构保存检测路径状态，实现回溯

页面功能测试，性能良好，超过88%在这里插入图片描述

import CheckFuncPerf as cfp

class Solution:
 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

aSolution = 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 执行结果 = True

4. 最优算法

根据本地日志分析，最优算法为第1种方式【原始矩阵状态+回溯】exist_base

本题测试数据，似乎能推出以下结论：

  1. 字典过滤检测性能消耗极小
  2. 额外的数据存储，带来额外的性能消耗
  3. 在检测集合和字符串多样化的情况下，第二种算法其实是会表现更好
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 执行结果 = True

5. 相关资源

本文代码已上传到CSDN，地址：Python算法题源代码_LeetCode(力扣)_单词搜索

一日练，一日功，一日不练十日空

may the odds be ever in your favor ~

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/424862.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【Datawhale组队学习：Sora原理与技术实战】Attention

【Datawhale组队学习：Sora原理与技术实战】Attention

Attention Attention 注意力&#xff0c;从两个不同的主体开始。 论文&#xff1a;https://arxiv.org/pdf/1703.03906.pdf seq2seq代码仓&#xff1a;https://github.com/google/seq2seq 计算方法&#xff1a; 加性Attention&#xff0c;如&#xff08;Bahdanau attention&…
阅读更多...
electron-release-server部署electron自动更新服务器记录

electron-release-server部署electron自动更新服务器记录

目录 一、前言 环境 二、步骤 1、下载上传electron-release-server到服务器 2、宝塔新建node项目网站 3、安装依赖 ①npm install ②安装并配置postgres数据库 ③修改项目配置文件 ④启动项目 ⑤修改postgres的认证方式 ⑥Cannot find where you keep your Bower p…
阅读更多...
Sqli-labs靶场第12关详解[Sqli-labs-less-12]

Sqli-labs靶场第12关详解[Sqli-labs-less-12]

Sqli-labs-Less-12 #手工注入 post传参了 根据题目看&#xff0c;像一个登录页面&#xff0c;尝试使用布尔型盲注测试能否登录网站 1. Username输入a a" 测试是否会有报错&#xff0c;burp抓包 报错&#xff1a;syntax to use near "a"") and passw…
阅读更多...
【风格迁移】pix2pixHD：高分辨率图像生成

【风格迁移】pix2pixHD：高分辨率图像生成

pix2pixHD&#xff1a;高分辨率图像生成 提出背景问题1: 如何提高生成图像的照片级真实感和分辨率&#xff1f;问题2: 如何利用实例级别的对象语义信息进一步提高图像质量&#xff1f;问题3: 如何实现图像合成的多模态性&#xff0c;允许交互式对象编辑&#xff1f; pix2pixHD …
阅读更多...
Vue3中Vuex状态管理库学习笔记

Vue3中Vuex状态管理库学习笔记

1.什么是状态管理 在开发中&#xff0c;我们会的应用程序需要处理各种各样的数据&#xff0c;这些数据需要保存在我们应用程序的某个位置&#xff0c;对于这些数据的管理我们就称之为状态管理。 在之前我们如何管理自己的状态呢&#xff1f; 在Vue开发中&#xff0c;我们使用…
阅读更多...
02、MongoDB -- MongoDB 的安全配置（创建用户、设置用户权限、启动安全控制、操作数据库命令演示、mongodb 的帮助系统介绍）

02、MongoDB -- MongoDB 的安全配置（创建用户、设置用户权限、启动安全控制、操作数据库命令演示、mongodb 的帮助系统介绍）

目录 MongoDB 的安全配置演示前准备&#xff1a;启动 mongodb 服务器 和 客户端 &#xff1a;1、启动单机模式的 mongodb 服务器2、启动 mongodb 的客户端 MongoDB 的安全配置启动演示用到的 mongodb 服务器 和 客户端启动单机模式的 mongodb 服务器&#xff1a;启动 mongodb 的…
阅读更多...
光学遥感卫星分辨率的奥秘 ！！

光学遥感卫星分辨率的奥秘 ！！

文章目录 前言 1、光学遥感卫星分辨率的多维视角 &#xff08;1&#xff09;空间分辨率 &#xff08;2&#xff09;光谱分辨率 &#xff08;3&#xff09;辐射分辨率 &#xff08;4&#xff09;时间分辨率 2、光学遥感分辨率的重要性 3、遥感分辨率的挑战与进步 4、未来展望 总…
阅读更多...
《Spring Security 简易速速上手小册》第7章 REST API 与微服务安全（2024 最新版）

《Spring Security 简易速速上手小册》第7章 REST API 与微服务安全（2024 最新版）

文章目录 7.1 保护 REST API7.1.1 基础知识详解7.1.2 重点案例&#xff1a;使用 JWT 进行身份验证和授权案例 Demo 7.1.3 拓展案例 1&#xff1a;API 密钥认证案例 Demo测试API密钥认证 7.1.4 拓展案例 2&#xff1a;使用 OAuth2 保护 API案例 Demo测试 OAuth2 保护的 API 7.2 …
阅读更多...
【2024】利用python爬取csdn的博客用于迁移到hexo,hugo,wordpress...

【2024】利用python爬取csdn的博客用于迁移到hexo,hugo,wordpress...

前言 博主根据前两篇博客进行改进和升级 利用python爬取本站的所有博客链接-CSDN博客文章浏览阅读955次&#xff0c;点赞6次&#xff0c;收藏19次。定义一个json配置文件方便管理现在文件只有用户名称,后续可加配置读取用户名称&#xff0c;并且将其拼接成csdn个人博客链接ty…
阅读更多...
OpenChat：性能高达105.7%，第一个超越ChatGPT的开源模型？

OpenChat：性能高达105.7%，第一个超越ChatGPT的开源模型？

OpenChat&#xff1a;性能高达105.7%&#xff0c;第一个超越ChatGPT的开源模型&#xff1f; 前几天开源模型第一还是是Vicuna-33B、WizardLM&#xff0c;这不又换人了。对于开源模型的风起云涌&#xff0c;大家见怪不怪&#xff0c;不断更新的LLM榜单似乎也没那么吸引人了。 …
阅读更多...
数学建模【因子分析】

数学建模【因子分析】

一、因子分析简介 因子分析由斯皮尔曼在1904年首次提出&#xff0c;其在某种程度上可以被看成是主成分分析的推广和扩展。 因子分析法通过研究变量间的相关系数矩阵&#xff0c;把这些变量间错综复杂的关系归结成少数几个综合因子&#xff0c;由于归结出的因子个数少于原始变…
阅读更多...
C/C++工程师面试题（数据库篇）

C/C++工程师面试题（数据库篇）

索引的优缺点 索引是一种支持快速查找特定行的数据结构&#xff0c;如果没有索引&#xff0c;就需要遍历整个表进行查找。用于提高数据检索的速度和效率。 好处&#xff1a; 提高检索速度&#xff1a; 索引可以加快数据的检索速度&#xff0c;因为它们允许数据库系统直接定位到…
阅读更多...
Mysql学习之MVCC解决读写问题

Mysql学习之MVCC解决读写问题

多版本并发控制 什么是MVCC MVCC &#xff08;Multiversion Concurrency Control&#xff09;多版本并发控制。顾名思义&#xff0c;MVCC是通过数据行的多个版本管理来实现数据库的并发控制。这项技术使得在InnoDB的事务隔离级别下执行一致性读操作有了保证。换言之&#xff0…
阅读更多...
【Tomcat】The CATALINA_HOME environment variable is not defined correctly

【Tomcat】The CATALINA_HOME environment variable is not defined correctly

文章目录 一、问题二、解决办法三、优化 一、问题 运行绿色版Tomcat时&#xff0c;单击apache-tomcat-9.0.27\bin\startup.bat时窗口一闪而过。 检查JAVA_HOME环境变量&#xff0c;可以发现并没有问题。 为了检查错误&#xff0c;将startup.bat程序使用文本编辑器打开&#x…
阅读更多...
Debezium发布历史163

Debezium发布历史163

原文地址&#xff1a; https://debezium.io/blog/2023/09/23/flink-spark-online-learning/ 欢迎关注留言&#xff0c;我是收集整理小能手&#xff0c;工具翻译&#xff0c;仅供参考&#xff0c;笔芯笔芯. Online machine learning with the data streams from the database …
阅读更多...
C++_程序流程结构_选择结构_switch

C++_程序流程结构_选择结构_switch

作用 执行多条件分支语句 语法 if和switch区别 switch 缺点&#xff0c;判断的时候只能是整形或者字符型&#xff0c;不可以是一个区间switch 优点&#xff0c;结构清晰&#xff0c;执行效率高
阅读更多...
go 命令行框架cobra

go 命令行框架cobra

go 命令行框架cobra go 拉取依赖包go get github.com/spf13/cobra 认识spf13/cobra-cli. cobra 命令行框架在golang中的地位也算得上是大明星级别。像k8s,docker都有使用这个框架构建自己命令行这块的功能. 最最最简单的开始----使用命令行工具cobra-cli来初始化你的demo c…
阅读更多...
四种策略改进的麻雀算法！效果起飞！你确定不来看看吗？

四种策略改进的麻雀算法！效果起飞！你确定不来看看吗？

声明&#xff1a;文章是从本人公众号中复制而来&#xff0c;因此&#xff0c;想最新最快了解各类智能优化算法及其改进的朋友&#xff0c;可关注我的公众号&#xff1a;强盛机器学习&#xff0c;不定期会有很多免费代码分享~ 目录 效果展示&#xff1a; 改进策略详解&#…
阅读更多...
C语言——指针的进阶——第1篇——（第26篇）

C语言——指针的进阶——第1篇——（第26篇）

坚持就是胜利 文章目录 一、字符指针1、面试题 二、指针数组三、数组指针1、数组指针的定义2、&数组名 VS 数组名3、数组指针的使用&#xff08;1&#xff09;二维数组传参&#xff0c;形参是 二维数组 的形式&#xff08;2&#xff09;二维数组传参&#xff0c;形参是 指针…
阅读更多...
django的模板渲染中的【高级定制】：按数据下标id来提取数据

django的模板渲染中的【高级定制】：按数据下标id来提取数据

需求&#xff1a; 1&#xff1a;在一个页面中显示一张数据表的数据 2&#xff1a;不能使用遍历的方式 3&#xff1a;页面中的数据允许通过admin后台来进行修改 4&#xff1a;把一张数据表的某些内容渲染到[xxx.html]页面 5&#xff1a;如公司的新商品页面&#xff0c;已有固定的…
阅读更多...
最新文章

Copyright @ 2022~2023