LF.82.Remove Adjacent Repeated Characters IV

Repeatedly remove all adjacent, repeated characters in a given string from left to right.<br /><br />No adjacent characters should be identified in the final string.<br /><br />Examples<br /><br />"abbbaaccz" → "aaaccz" → "ccz" → "z"<br />"aabccdc" → "bccdc" → "bdc"<br /><br />方法1，用stack

public String deDup(String input) {
        // Write your solution here
        if (input == null){
            return null ;
        }
        if (input.length() == 0){
            return input;
        }
        //use a stack to store the visited value, if repeat then pop
        Deque<Character> stack = new LinkedList<>() ;
        stack.push(input.charAt(0));
        for (int i = 0; i < input.length() ; ) {
            if (stack.size() == 0){
                stack.push(input.charAt(i));
                i++;
                continue;
            }
            if (stack.size() > 0 && stack.peek() != input.charAt(i) ){
                stack.push(input.charAt(i));
                i++;
            } else if (stack.peek() == input.charAt(i)){
                // stack contains [a,b] b on top
                Character value = stack.peek() ;
                //skip all the b
                while (i<input.length() && input.charAt(i) == value){
                    i++ ;
                }
                stack.pop();
            }
        }
        char[] res = new char[stack.size()] ;
        for (int i = stack.size()-1; i >=0 ; i--) {
            res[i] = stack.pop() ;
        }
        return new String(res) ;
    }

方法2， 不用stack 通过控制指针来做到

public String deDup_noStack(String input) {
         // Write your solution here
         if (input == null){
             return null ;
         }
         if (input.length() <= 1){
             return input;
         }
         //use a stack to store the visited value, if repeat then pop
         char[] chars = input.toCharArray();
         /*
         instead of using a extra stack explicitly, we can actually
         reuse the left side of the original char[] as the "stack"
         end(including) serves as the stack to be kept
         * */
         //
         int end = 0 ;
         for (int i = 1; i < chars.length; i++) {
             //if the stack is empty or no dup.
             if (end == -1 || chars[end] != chars[i]){
                 chars[++end] = chars[i];
             } else{
                 //otherwise, we need pop the top element by end--
                 //and ignore all the consecutive duplicate chars.
                 end--;
                 //whenever you use i+1, check out of boundary
                 while (i+1< chars.length && chars[i] == chars[i+1]){
                     i++;
                 }
             }
         }
         //end is index, count is length
         return new String(chars, 0 , end+1) ;
     }

<br /><br />