本文主要是介绍【leetcode——栈的题目】——1003. 检查替换后的词是否有效python,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:
给你一个字符串 s
,请你判断它是否 有效 。
字符串 s
有效 需要满足:假设开始有一个空字符串 t = ""
,你可以执行 任意次 下述操作将 t
转换为 s
:
- 将字符串
"abc"
插入到t
中的任意位置。形式上,t
变为tleft + "abc" + tright
,其中t == tleft + tright
。注意,tleft
和tright
可能为 空 。
如果字符串 s
有效,则返回 true
;否则,返回 false
。
示例 1:
输入:s = "aabcbc" 输出:true 解释: "" -> "abc" -> "aabcbc" 因此,"aabcbc" 有效。
示例 2:
输入:s = "abcabcababcc" 输出:true 解释: "" -> "abc" -> "abcabc" -> "abcabcabc" -> "abcabcababcc" 因此,"abcabcababcc" 有效。
示例 3:
输入:s = "abccba" 输出:false 解释:执行操作无法得到 "abccba" 。
提示:
1 <= s.length <= 2 * (10 ** 4)
s
由字母'a'
、'b'
和'c'
组成
题解:
一.需要的知识
这道题需要用到一个数据结构,它的名字叫栈 ,那么什么是栈呢?
数据结构中的栈(Stack)是一种特殊的线性数据结构,它遵循后进先出(LIFO,Last In First Out)的原则。这意味着最后一个被放入栈中的元素将是第一个被取出的元素。栈通常用于处理需要按特定顺序执行的任务,例如函数调用和递归、括号匹配、表达式求值等。
还是不懂?
这会直接懂了吧~
那么在python中怎么操作呢?
1.创建栈
在Python中,你可以简单地通过创建一个空列表来初始化一个栈。
stack = [] |
2.入栈(Push)
使用列表的append()
方法可以将元素添加到栈顶。
stack.append('A') # 将元素'A'入栈 | |
stack.append('B') # 将元素'B'入栈 |
3.出栈(Pop)
使用列表的pop()
方法并指定索引为-1可以移除并返回栈顶的元素。
top_element = stack.pop(-1) # 出栈操作,移除并返回栈顶元素,这里是'B' |
如果不传递索引给pop()
方法,它默认会弹出列表中的最后一个元素,这正是我们想要的栈行为。
top_element = stack.pop() # 同样是出栈操作,移除并返回栈顶元素 |
4.查看栈顶元素(Peek 或 Top)
你可以通过索引-1来查看栈顶元素,但不移除它。
top_element = stack[-1] # 查看栈顶元素,这里是'A' |
5.判断栈是否为空
使用列表的长度来判断栈是否为空。
is_empty = len(stack) == 0 # 如果栈的长度为0,则为空 |
6.获取栈的大小
使用len()
函数来获取栈中元素的数量。
stack_size = len(stack) # 获取栈的大小 |
二.题解
class Solution:def isValid(self, s: str) -> bool:#1.字符串存在包含关系#2.数据结构为栈#3.只管a和c如果栈中无a但是遇到了入栈的c那么就是False#4.遇到ab就入栈即可#5.如果遇到c,那就判断栈的顶是不是b和栈顶的前一个是不是astack = []for i in range(len(s)):if s[i] == "c":if len(stack) < 2:return False elif stack.pop(-2) != "a" or stack.pop() != "b":return False else:stack.append(s[i])if len(stack) != 0:return Falsereturn True
题解在这里,如果是刚遇到这种数据结构的小伙伴,建议做一下这道题:20. 有效的括号
做完之后再来看这道题,或许就能了解很多。
结尾:
如果想刷力扣题没有团队没有动力怎么办?大家可以加入我的刷题群,一起刷题,有想进群的可以在底下评论:进群0.0
感谢大家的浏览,如有错误,望指正。
这篇关于【leetcode——栈的题目】——1003. 检查替换后的词是否有效python的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!