leetcode 1003. 检查替换后的词是否有效

题目

方法一（速度最慢）

思路 这是我最先想到的方法，每碰到一个“abc”，就删除该“abc”，最后看看字符串长度是否为0 时间 875ms 代码

class Solution { public boolean isValid(String S) { if(!S.contains("abc")){ return false; } int index=S.indexOf("abc"); while(index!=-1){ if(S.equals("abc"))return true; S=S.substring(0,index)+S.substring(index+3); // System.out.println(S); index=S.indexOf("abc"); } if(S.length()>0){ // System.out.println("3"); return false; }else{ return true; } } }

方法二（代码最简单，速度尚可）

思路 把字符串中的“abc”不停的替换为“” 时间 69ms 代码

class Solution { public boolean isValid(String S) { if(!S.contains("abc")){ return false; } while(S != ""&&S.indexOf("abc")!=-1){ S=S.replaceAll("abc",""); } return S.length()==0; } }

方法三（速度最快）

思路

遍历字符串，在abc中的ab中插入abc（aabcb），在bc中插入abc（babcc），在a前面插入abc（abca）由上可知，a的前面可以为a、b、c，b的前面只能为a、c，c的前面只能为b、c遍历字符串，碰到a，flag+1，碰到c，flag-1，如果flag<0，证明c和a的位置出现了颠倒，则返回false

时间

8 ms 代码

class Solution { public boolean isValid(String S) { int flag=0; char pre='1'; for(char ch:S.toCharArray()){ switch(ch){ case 'a': flag++; break; case 'b': if(pre=='b'){ return false; } break; case 'c': if(pre=='a'){ return false; } flag--; if(flag<0)return false; break; } pre=ch; } return flag==0; } }