当前位置: 首页> 健康> 母婴 > 济宁疫情最新情况_重庆网站优化_百度收录api怎么提交_免费外链生成器

济宁疫情最新情况_重庆网站优化_百度收录api怎么提交_免费外链生成器

时间:2025/7/9 16:27:56来源:https://blog.csdn.net/sjsjs11/article/details/143316738 浏览次数:0次
济宁疫情最新情况_重庆网站优化_百度收录api怎么提交_免费外链生成器

给你一个字符串 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” 。
在这里插入图片描述

模拟栈

class Solution {
public:bool isValid(string s) {string st;for(char c : s){st.push_back(c);if(st.size() >= 3 && st.substr(st.size() - 3, 3) == "abc"){st.erase(st.end() - 3, st.end());}}return st.empty();}
};

时间复杂度:O(n),其中 n 是字符串 s 的长度。

空间复杂度:O(n)。栈需要占用 O(n) 的空间。

我们可以采用模拟栈的方法,由于一开始t字符串第一次操作后一定是"abc",所以我们可以一旦遇到abc,就将它消除。在栈中表现为如果栈顶三个元素为"abc",那么就将它弹出,最后如果st变为空,则说明可以通过将字符串 “abc” 插入到 t 中的任意位置,得到字符串s。

关键字:济宁疫情最新情况_重庆网站优化_百度收录api怎么提交_免费外链生成器

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: