鱼C论坛

 找回密码
 立即注册
查看: 63|回复: 0

[学习笔记] 论.技术.Python.(新)零学Python作业第33讲:“双指针”追踪判断字符串子序列

[复制链接]
发表于 2022-9-23 16:23:57 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 小蜂队 于 2022-9-25 15:20 编辑

0.判断子序列
给定字符串 s 和 t ,请编程判断 s 是否为 t 的子序列。
字符串的子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串(例如,"ace" 是 "abcde" 的子序列,而 "aec" 则不是)。
153611clb1honln1icin0b.png
  1. s = input("请输入字符串s:")
  2. t = input("请输入字符串t:")
  3.    
  4. n = len(s)
  5. m = len(t)
  6.    
  7. j = k = 0
  8. while j < n and k < m:
  9.     if s[j] == t[k]:
  10.         j += 1
  11.     k += 1
  12.    
  13. if j == n:
  14.     print("字符串 s 是字符串 t 的子序列。")
  15. else:
  16.     print("字符串 s 不是字符串 t 的子序列。")
复制代码

解析:代码清单的解题思路是利用了 “双指针” 追踪的方法。
j 和 k 是两个负责追踪匹配的指针,分别指向字符串 s 和 t 的初始位置,然后每次判断 s[j] 与 t[k] 是否相等,如果相等则两个追踪指针同时移动到下一个位置继续判断。
由于 “子序列” 的判定是允许中间 “删除一些字符”,因此每当 s[j] 与 t[k] 不相等的时候,k 指针移动到下一位,继续尝试匹配。
最终如果 j 等于字符串 s 的长度,也就说明了 s 整个字符串成功地被遍历了一遍,即证明 s 是 t 的子序列。

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1

GMT+8, 2022-10-3 02:42

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表