Leetcode-1047-Remove All Adjacent Duplicates In String

Remove All Adjacent Duplicates In String

leetcode: https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/

Description:

You are given a string s consisting of lowercase English letters. A duplicate removal consists of choosing two adjacent and equal letters and removing them.

We repeatedly make duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made. It can be proven that the answer is unique.

Idea:

**solution **

Step1: set the stack to record result

Step2: Stack is FILO, so if the top element is the equal to current element in the traversal, it means they are adjanct duplicates, pop the elment in the stack. otherwise, push this element to the stack.

Step3: because Stack is FILO, so we need to reverse elements in the stack. create a string to record reversed stack’s element.

Code:

class Solution {
    public String removeDuplicates(String s) {
        //create the stack to record the result
        Stack<Character> result = new Stack<>();
        //traverse the string
        for(int i=0; i<s.length(); i++){
            //if the current element isn't equal to the top element of the stack, add it to stack
            if(result.isEmpty() || s.charAt(i) !=result.peek()){
                result.push(s.charAt(i));
            }
            //if they are equal, we need to remove the elment in the stack
            else{
                result.pop();
            }
        }
        //create the string and reverse element's order of the stack
        String string1= "";
        while(!result.isEmpty()){
            string1 = result.pop() + string1;
        }
        return string1;
    }
}