【算法】Check If Word Is Valid After Substitutions 检查替换后的词是否有效-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】Check If Word Is Valid After Substitutions 检查替换后的词是否有效。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Check If Word Is Valid After Substitutions 检查替换后的词是否有效

问题描述：

给你一个字符串 s ，请你判断它是否有效。
字符串 s 有效需要满足：假设开始有一个空字符串 t = “” ，你可以执行任意次下述操作将 t 转换为 s ：

将字符串 “abc” 插入到 t 中的任意位置。形式上，t 变为 tleft + “abc” + tright，其中 t == tleft + tright 。注意，tleft 和 tright 可能为空。
如果字符串 s 有效，则返回 true；否则，返回 false。
s.length范围 $[1, 20000]$ ,仅由abc构成。

分析

使用暴力构造的方法，就是每构造一个有效的 $s^{'}$ ，然后在 $s^{'}$ 的每个位置上插入 $ab c$ ，直到达到目标的 $s$ 长度。但是 $s^{'}$ 越长，枚举的位置越多，时间复杂度也越大。

同样逆向的做dfs，每次找到一个abc，然后删除，但是这样也会面临相同的问题。

还有一种暴力的思路，就是 $re pl a ce$ ，每一次将所有符合条件的abc，全部用空字符串替换，直到整个 $s$ ，不存在 $ab c$ ，判断s是否是空字符串。
replace作为封装的string API，确实可以处理这个问题，但是另一方面，这个replace过程中对空间，时间上的消耗，可以思考一下。

这个问题可以抽象成为一个栈，类似于括号匹配。abc可以抽象的作为一个 $()$ ,

遇到字符 $a$ ，可以直接入栈。
遇到字符b,如果要符合条件，那么此时栈顶必须是a，也就是说，如果栈空或者栈顶 $t o p! = a$ ,说明无法满足题目的条件，返回 $f a l se$ 。否则可以将栈顶 $修改为 b$ 。
遇到字符c，其实和字符b是一样的处理，也是只关心栈顶是否是b。

整个流程遍历一次，最大的空间就是开栈，时间复杂度** $O (N)$ ，空间** $O (N)$ 。

时间复杂度 $O (N)$
空间复杂度： $O (N)$

代码

public boolean isValid(String s) {
        while(s.indexOf("abc")!=-1){
            s = s.replace("abc","");
        }
        return s.equals("");
    }

时间复杂度 $O (N)$
空间复杂度： $O (N)$

 public boolean isValid(String s) {
        Deque<Integer> st = new ArrayDeque();
        for(int i=0;i<s.length();i++){
            int c = s.charAt(i)-'a';
            if(c==0){
                st.push(c);
                continue;
            }
            if(st.isEmpty()) return false;
            int top = st.pop();
            if(c-top!=1)return false;
            if(c==1){
                st.push(c);
            } 
        } 
        return st.isEmpty(); 
    }