当前位置：首页 > article >正文

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

article 2024/9/22 3:45:29

文章目录

Check If Word Is Valid After Substitutions 检查替换后的词是否有效
- 问题描述：
- 分析
- 代码
Tag

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’的每个位置上插入abc，直到达到目标的s长度。但是s’越长，枚举的位置越多，时间复杂度也越大。
同样逆向的做dfs，每次找到一个abc，然后删除，但是这样也会面临相同的问题。

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

这个问题可以抽象成为一个栈，类似于括号匹配。abc可以抽象的作为一个(),遇到字符a，可以直接入栈。遇到字符b,如果要符合条件，那么此时栈顶必须是a，也就是说，如果栈空或者栈顶!=a,说明无法满足题目的条件，返回false。否则可以将栈顶修改为b。遇到字符c，其实和字符b是一样的处理，也是只关心栈顶是否是b。
整个流程遍历一次，最大的空间就是开栈，时间复杂度ON，空间ON。

时间复杂度 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(); 
    }