网站要素,wordpress 副标题 seo,留学网站建设文案,企业网站优化暴肃湖南岚鸿很好1. 题目
给定有效字符串 “abc”。
对于任何有效的字符串 V#xff0c;我们可以将 V 分成两个部分 X 和 Y#xff0c;使得 X Y#xff08;X 与 Y 连接#xff09;等于 V。#xff08;X 或 Y 可以为空。#xff09;那么#xff0c;X “abc” Y 也同样是有效的。
例…1. 题目
给定有效字符串 “abc”。
对于任何有效的字符串 V我们可以将 V 分成两个部分 X 和 Y使得 X YX 与 Y 连接等于 V。X 或 Y 可以为空。那么X “abc” Y 也同样是有效的。
例如如果 S “abc”则有效字符串的示例是“abc”“aabcbc”“abcabc”“abcabcababcc”。无效字符串的示例是“abccba”“ab”“cababc”“bac”。
如果给定字符串 S 有效则返回 true否则返回 false。
示例 1
输入aabcbc
输出true
解释
从有效字符串 abc 开始。
然后我们可以在 a 和 bc 之间插入另一个 abc产生 a abc bc即 aabcbc。示例 2
输入abcabcababcc
输出true
解释
abcabcabc 是有效的它可以视作在原串后连续插入 abc。
然后我们可以在最后一个字母之前插入 abc产生 abcabcab abc c即 abcabcababcc。示例 3
输入abccba
输出false示例 4
输入cababc
输出false提示
1 S.length 20000
S[i] 为 a、b、或 c来源力扣LeetCode 链接https://leetcode-cn.com/problems/check-if-word-is-valid-after-substitutions 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
首先字符串长度必须为3的倍数且以 a 开始采用栈将 ab 压栈遇到 c 的时候出栈且栈顶必须为 b后续为 a最后栈为空才全部匹配了
class Solution {
public:bool isValid(string S) {if(S.size()%3 ! 0 || S[0] ! a)return false;stackchar stk;for(int i 0; i S.size(); i){if(S[i] c){if(stk.empty() || (!stk.empty() stk.top() ! b))return false;else{stk.pop();if(stk.empty() || (!stk.empty() stk.top() ! a))return false;elsestk.pop();}}elsestk.push(S[i]);}return stk.empty();}
};
