Leetcode skimming: stack and queue 04 (delete all adjacent duplicates in the string)

1047. Delete all adjacent duplicates in the string

Force button topic link

Give a string of lowercase letters S, Duplicate deletion selects two adjacent and identical letters , And delete them .

stay S Repeat the delete operation on , Until you can't delete .

Returns the final string... After all the duplicates have been deleted . The answer is guaranteed to be unique .

Example ：

• Input ：“abbaca”
• Output ：“ca”
• explain ： for example , stay “abbaca” in , We can delete “bb” Because two letters are adjacent and the same , This is the only duplicate that can be deleted at this time . And then we get the string “aaca”, There is only “aa” You can perform a duplicate deletion operation , So the last string is “ca”.

Tips ：

• 1 <= S.length <= 20000
• S It's only made up of lowercase letters .

Put the elements on the stack in reverse order , When entering, judge whether it is the same as the top element , The same is not true , Instead, it comes out of the stack . Finally, traverse the stack to get the result . Inverse is positive , This is the desired result . It feels easier to do double pointer . I'll try .

package com.programmercarl.stacks_queues;

import java.util.Stack;

/** * @ClassName RemoveDuplicates * @Descriotion TODO * @Author nitaotao * @Date 2022/6/29 18:04 * @Version 1.0 * https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/ * 1047.  Delete all adjacent duplicates in the string  **/
public class RemoveDuplicates {
    
    /** *  This problem can be solved by double pointer method , Stacks can do it, too  * * @param s * @return */
    public static String removeDuplicates(String s) {
    
        String result = "";
        char[] chars = s.toCharArray();
        Stack<Character> stack = new Stack();
        for (int i = chars.length - 1; i >= 0; i--) {
    
            // Directly stack when there is no element 
            if (stack.size() == 0) {
    
                stack.push(chars[i]);
            } else if (stack.peek() != chars[i]) {
    
                // If the current element is different from the top element , Push 
                stack.push(chars[i]);
            } else {
    
                stack.pop();
            }
        }
        while (stack.size() != 0) {
    
            result += stack.pop();
        }
        return result;
    }

    public static void main(String[] args) {
    
        System.out.println(removeDuplicates("abbaca"));
    }
}

My attempt to write double pointer failed

         char[] chars = s.toCharArray();
        int right = 0;
        int left = 0;
        while (right < s.length()) {
    
            chars[left] = chars[right];
            if (left > 0 && chars[left] == chars[left - 1]) {
    
                left--;
            } else {
    
                left++;
            }
            right++;
        }
        return new String(chars, 0, left);

Similar to the sum of three numbers , The left side is relatively fixed , Slide right .