646. 最长数对链 - Kotlin 动态规划+贪心

原题地址：https://leetcode.cn/problems/check-if-word-is-valid-after-substitutions/

题解

当我们插入i次abc时，由于没有后续插入，第i次插入的abc一定在s中的某个位置以连续的“abc”形式存在，当我们删除这个连续的“abc”时，实际上相当于将s还原到了第i-1次插入的情况

如果s是有效的，则我们可以不断迭代到第0次插入，即将s还原回空字符串的情况。如果还原到最后无法使s变为空字符串，则说明该字符串无效

我们可以用一个数组模拟栈，用i遍历s，每次将i插入数组末尾，如果数组末尾的三个字符满足一个连续的“abc”，则我们将其删除，如果遍历完毕后数组为空（需要用一个top指针来维护数组长度），则说明s有效

时间复杂度：O(N)

空间复杂度：O(N)

class Solution {
    static char[] stack=new char[20001];
    public boolean isValid(String s) {
        if(s.length()%3!=0)return false;
        char[] sarr=s.toCharArray();
        int top=-1;//top -1则说明当前栈为空
        for (int i=0;i<sarr.length;i++){
            if(sarr[i]=='c'&&top+1>=2&&stack[top]=='b'&&stack[top-1]=='a'){
                top-=2;//满足连续的abc则将栈顶的a和b出栈
            }else{
                stack[++top]=sarr[i];//不满足则入栈
            }
        }
        return top==-1;//返回栈是否为空
    }
}