【算法】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’的每个位置上插入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(); }

代码还可以再压缩，但是基本流程是这样。

Tag

栈