刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

合法出栈序列

给定一个由不同小写字母构成的长度不超过8的字符串x,现在要将该字符串的字符依次压入栈中,然后再全部弹出。

要求左边的字符一定比右边的字符先入栈,出栈顺序无要求。

再给定若干字符串,对每个字符串,判断其是否是可能的x中的字符的出栈序列。

时间限制:1000

内存限制:65536

输入

第一行是原始字符串x 后面有若干行,每行一个字符串

输出

对除第一行以外的每个字符串,判断其是否是可能的出栈序列。如果是,输出"YES",否则,输出"NO"

样例输入

abc

abc

bca

cab

样例输出

YES

YES

NO

使用微信搜索喵呜刷题,轻松应对考试!

答案:

解析:

【喵呜刷题小喵解析】:这个问题可以通过模拟栈的操作来解决。对于每个待判断的字符串,我们遍历它的每个字符,同时维护一个栈来模拟入栈和出栈操作。在遍历字符串的字符时,我们需要考虑两个条件:1. 左边的字符一定比右边的字符先入栈,这意味着栈顶元素必须小于或等于当前字符。2. 出栈顺序无要求,这意味着栈顶元素可能是原始字符串中任何一个字符。因此,我们可以按照以下步骤进行模拟:1. 初始化一个空栈。2. 遍历待判断字符串的每个字符:* 如果栈不为空且栈顶元素小于当前字符且在原始字符串中栈顶元素的索引大于当前字符的索引,那么将栈顶元素出栈,直到满足条件1或栈为空。* 如果栈为空或栈顶元素大于等于当前字符,将当前字符入栈。* 如果栈顶元素小于当前字符且在原始字符串中栈顶元素的索引小于当前字符的索引,那么当前字符串不是合法的出栈序列,返回False。3. 如果遍历完待判断字符串后栈为空,那么它是合法的出栈序列,返回True,否则返回False。在主程序中,我们首先读入原始字符串,然后循环读入待判断字符串,对每个待判断字符串调用is_valid_sequence函数判断其是否是合法的出栈序列,并输出结果。时间复杂度为O(n*m),其中n是待判断字符串的数量,m是字符串的长度。空间复杂度为O(m),主要是栈的空间。
创作类型:
原创

本文链接:合法出栈序列 给定一个由不同小写字母构成的长度不超过8的字符串x,现在要将该字符串的字符依次压入栈中

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share