LeetCode刷题之392.判断子序列
程序员文章站
2022-07-12 08:55:26
...
LeetCode刷题之392.判断子序列
我不知道将去向何方,但我已在路上! |
---|
时光匆匆,虽未曾谋面,却相遇于斯,实在是莫大的缘分,感谢您的到访 ! |
-
题目:
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。 - 注意:
- 十六进制中所有字母(a-f)都必须是小写。
- 十六进制字符串中不能包含多余的前导零。如果要转化的数为0,那么以单个字符’0’来表示;对于其他情况,十六进制字符串中的第一个字符将不会是0字符。
- 给定的数确保在32位有符号整数范围内。
- 不能使用任何由库提供的将数字直接转换或格式化为十六进制的方法。
- 示例:
示例 1:
s = "abc", t = "ahbgdc"
返回 true.
示例 2:
s = "axc", t = "ahbgdc"
返回 false.
- 代码1:
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
s,t = list(s),list(t)
while s != [] and t != []:
if s[-1] == t[-1]:
s.pop()
t.pop()
continue
t.pop()
if s == []:
return True
return False
# 执行用时 :272 ms, 在所有 python3 提交中击败了30.81%的用户
# 内存消耗 :20.8 MB, 在所有 python3 提交中击败了5.26%的用户
-
算法说明:
先将s和t转换为列表格式,然后采用pop函数从后往前进行判断,如果s的最后一个和t的最后一个字符一样,则弹出s和t的最后一个字符,如果,最后一个字符不一样,只将t的最后一个字符弹出,当s和t中有一个为空的时候,循环结束;判断s是否为空,如果为空,返回True,否则返回False。 - 代码2:
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
i,j = 0,0
while i < len(s) and j < len(t):
if s[i] == t[j]:
i += 1
j += 1
else:
j += 1
if i == len(s):
return True
return False
# 执行用时 :376 ms, 在所有 python3 提交中击败了12.99%的用户
# 内存消耗 :18.3 MB, 在所有 python3 提交中击败了5.26%的用户
-
算法说明:
采用正序方式遍历s和t中的元素,如果s的当前元素和t的当前元素一样,则将s和t的索引同时+1,如果不一样,只将t的索引+1,当s和t中有一个的索引达到最大索引时,循环结束;判断s的索引是否达到最大,如果达到最大,返回True,否则返回False。
下一篇: 动态规划——最长公共子序列