Given a string s, determine if it is valid.
A string s is valid if, starting with an empty string t = "", you can transform t into s after performing the following operation any number of times:
Insert string "abc" into any position in t. More formally, t becomes tleft + "abc" + tright, where t == tleft + tright. Note that tleft and tright may be empty.Return true if s is a valid string, otherwise, return false.
Example 1:
Input: s = "aabcbc" Output: true Explanation: "" -> "abc" -> "aabcbc" Thus, "aabcbc" is valid.Example 2:
Input: s = "abcabcababcc" Output: true Explanation: "" -> "abc" -> "abcabc" -> "abcabcabc" -> "abcabcababcc" Thus, "abcabcababcc" is valid.Example 3:
Input: s = "abccba" Output: false Explanation: It is impossible to get "abccba" using the operation.Example 4:
Input: s = "cababc" Output: false Explanation: It is impossible to get "cababc" using the operation.
Constraints:
1 <= s.length <= 2 * 104s consists of letters 'a', 'b', and 'c'题目链接：https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/
题目意思就是可以任意位置插入“abc”,判断一个字符串是不是可以通过这个操作得到。
思路：这题和判断合法符号一个意思，用栈来解决，看到这个题我就想起来用栈stack了。
遍历字符串S，遇到不是'c'的字符，就压入栈，遇到是字符'c',就弹出栈的2个元素(要先判断栈内元素个数是不是大于 2 ，第一次没写这个判断，报错了，一时没想起来)，看看依次是不是'b',‘a’(这个需要判断，如果'a','b',那就是不合法的）。
class Solution { public: bool isValid(string s) { stack<char> stk; char tmp; for(auto c:s) { if(c!='c') { stk.push(c); } else { if(!stk.empty())//遇到'c'但是栈里不是空的 { if(stk.size()<2)//栈里元素小于 2 个，直接返回false，这个判断不能忘，不然空栈还top()会报错 { return false; } tmp=stk.top();//此处还是要判断依次弹出的是不是 ‘b’ 'a' if(tmp!='b') { return false; } stk.pop();//top()返回栈顶元素（不删除），pop()删除并返回栈顶元素 tmp=stk.top(); if(tmp!='a') { return false; } stk.pop(); } else//遇到'c'但是栈里是空的就可以直接返回false { return false; } } } return stk.size()==0; } };
