前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Python 刷题笔记:随缘题目

Python 刷题笔记:随缘题目

作者头像
TTTEED
发布2020-07-08 18:26:45
6240
发布2020-07-08 18:26:45
举报
文章被收录于专栏:用户6811391的专栏

今天时间不太多,记一道遇到的面试题:

题目

给定一个 m x n 的字符矩阵和字符串 s,在矩阵中每次只能横向、纵向移动一步,不能超出矩阵范围,问:是否可以由矩阵中拼接出 s?

题目分析

对深度优先搜索掌握并不到位,所以第一时间没有形成思路。直到后来确定是应用该算法后,才刚刚把答案完成。大致思路:用嵌套的列表来表示矩阵,首先遍历矩阵中的点,找到可以匹配字符串起点的点。

匹配到起点后,由该起点移动位置看能否完整匹配字符串 s,若可以、返回 True。将这个过程定义成独立的函数,在每次匹配到起点后调用,若全部起点都不能达到目标,最终返回 False。

代码实现

代码语言:javascript
复制
# 由矩阵中点向上下左右移动检索的函数def search(tup,matrix,s):    # 如果字符串为空,单独处理    if not s:        return (-2,-2)    # 要匹配的字符 c 为字符串首字符    c = s[0]    # 获取当前被检测点坐标    i,j = tup    # 获取坐标范围    x = len(matrix)    y = len(matrix[0])    # 在边界范围内上下左右移动一格进行匹配检测,若成功,返回移动后坐标    if j>0:        if matrix[i][j-1]==c:            return (i,j-1)    if j<y-1:        if matrix[i][j+1]==c:            return (i,j+1)    if i>0:        if matrix[i-1][j]==c:            return (i-1,j)    if i<x-1:        if matrix[i+1][j]==c:            return (i+1,j)    # 若均不匹配成功,返回 (-1,-1)    return (-1,-1)
# 定义判断函数,输入矩阵 matrix 字符串 s    def judge(matrix,s):    # 判断匹配是否成功的变量    match = False    # 行坐标范围    row_l = len(matrix[0])    # 列坐标范围    col_l = len(matrix)    # 在行、列范围内遍历点 (p,q)    for p in range(col_l):        for q in range(row_l):          # 如果(p,q)可以匹配字符串起点            if matrix[p][q]==s[0]:              # 复制下坐标                a,b = p,q                # 先将match赋值 True                match = True                # 如果被匹配字符串非空                while s:                  # 字符串去掉首位重新赋值                    s = s[1:]                    # 调用检索函数,结果重新赋值给 a,b                    a,b = search((a,b),matrix,s)                    # 若函数返回 (-1,-1),匹配失败,跳出 while循环                    if a==-1:                        match = False                        break                # 若while循环完整结束,则匹配成功,直接返回 True                    if match:                    return True    # 若中途未成功,返回 False    return False
matrix = [["a","b","c"],["k","f","g"],["e","a","k"],["p","m","n"]]s = "ekabd"s2 = "kfg"print(judge(matrix,s))print(judge(matrix,s2))

结论

第一次遇到深度优先搜索真题,有些懵,算是挺失败的经历,上面的代码也只是简单通过了能想到的测试例子,还是存在漏洞的,之后如果刷到更完善的题目再进行优化。

不过感觉也还不错,之前的一系列练习也有效果,在有了深度优先搜索概念后也能独立完成了,就是时间花费的有些夸张,继续努力吧!

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2020-05-15,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 TTTEED 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
    • 题目分析
      • 代码实现
      • 结论
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档