题目描述

给你一个字符串 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 * 104
s 由字母 ‘a’、‘b’ 和 ‘c’ 组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/check-if-word-is-valid-after-substitutions
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

栈的应用
遍历字符串，如果遇到’a’、‘b’入栈；遇到’c’，出栈两个字符，判断这两个字符是否分别为’b’、‘a’。

代码

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        for(char c:s.toCharArray()){
            if(c!='c'){
                stack.push(c);
            }else{
                if(stack.size()<2){
                    return false;
                }
                char m=stack.pop();
                char n=stack.pop();
                if(m!='b' || n!='a'){
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}