1047. Remove All Adjacent Duplicates In String

Link

難易度 : Easy

question

題目給予一個string，並且要求消去相鄰的相同字母並且用消去後的string繼續消去
概念上類似小時候玩的一個遊戲祖瑪，相同色的消除後，左右合併繼續判斷

我的思路是使用stack

peek判斷與前一個相不相同，相同則pop處理，不相同就push進去
將stack轉為string後return

    //with stack
    class Solution {
        public String removeDuplicates(String s) {
            char[] chars = s.toCharArray();
            Stack<Character> stack = new Stack<Character>();
            for(int i=0;i<chars.length;i++) 
            {
                //判斷當前char是否與stack最後的字元一樣 如果是的話要消除
                if(!stack.isEmpty()&&stack.peek()==chars[i]) 
                {
                    stack.pop();
                }
                else 
                {
                    stack.push(chars[i]);
                }
            }

            char[] result = new char[stack.size()];
            for(int i=result.length-1;i>=0;i--) 
            {
                result[i] = stack.pop();
            }
            return new String(result);
        }
    }

result

可以看到效率非常地低下，一開始研究了一下發現也許可能是stack在轉型成string的過程會花去很多時間，因此修改了一下程式，使用StringBuilder來建構字串，並且遇到相同的時候將sb中的字元刪除

    //with stringbuilder
    class Solution2 {
        public String removeDuplicates(String s) {
            StringBuilder sb = new StringBuilder();
            for(int i = 0 ;i<s.length();i++) 
            {
                //判斷sb最後一個字是否與當前字元相同  一樣的話要消除
                if(sb.length()>0&&sb.charAt(sb.length()-1)==s.charAt(i)) 
                {
                    sb.deleteCharAt(sb.length()-1);
                }
                else 
                {
                    sb.append(s.charAt(i));
                }
            }
            return sb.toString();
        }
    }

result2

結果效率上的確有提升，但提昇的有限QQ
於是乎又再研究了一下，發現也許是重複操作字元的填入予刪除的過程白做工，於是想到了若是可以在陣列上直接操作填入Char的話也許可以更快一些

這時候我想到了一個好東西

快慢指針

再更之前的題目寫到很多可以運用到快慢針的作法，於是這邊嘗試將快慢指針運用在這個題目上

解題思路

使用char[] chars來直接紀錄結果
slow用來標記需要填入的index並且同時代表最後result的length
fast代表遍歷string的指針
填入字元前先判斷當前字元chars[fast]是否與前一個的字元chars[slow-1]相同
True. 若是相同則不填入且slow需要退回前一位以便後續填入其他字元覆蓋
False. 若是不相同則可以填入

    //with two pointer
    class Solution {
        public String removeDuplicates(String s) {
            char[] chars = s.toCharArray();
            int slow,fast;
            for(slow=0,fast=0;fast<chars.length;fast++) 
            {               
                //若slow前一格與fast當前字元配對 代表配對了
                //slow需要退回前一格等待下一輪判斷
                if(slow>0&&chars[slow-1]==chars[fast]) 
                {
                    slow--;
                }
                else 
                {
                    //將slow位置填入chars[fast]
                    chars[slow] = chars[fast];
                    slow++;
                }
            }
            return new String(chars,0,slow);
        }
    }

result3