LeetCode（Stack)1047. Remove All Adjacent Duplicates In String

待我称王封你为后i 2023-09-25 21:33 90阅读 0赞

# 1.问题 #

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.

Example 1:

> Input: s = “abbaca”  
> Output: “ca”  
> Explanation:  
> For example, in “abbaca” we could remove “bb” since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is “aaca”, of which only “aa” is possible, so the final string is “ca”.

Example 2:

> Input: s = “azxxzy”  
> Output: “ay”

Constraints:

*  1 <= s.length <= 105
 *  s consists of lowercase English letters.

# 2. 解题思路 #

## 方法1： ##

> 1.  初始化一个栈
> 2.  遍历字符串中的每个字符
> 3.  如果栈不为空并且栈顶元素与当前字符相同，则弹出栈顶元素
> 4.  否则将当前字符压入栈中
> 5.  将栈中的元素转换成字符串

## 方法2： ##

> 1.  创建 StringBuilder 对象
> 2.  遍历字符串 s 的每个字符 记录当前
> 3.  StringBuilder 对象的长度 如果当前字符和StringBuilder 对象中最后一个字符相等 删除 StringBuilder 对象中最后一个字符
> 4.  如果当前字符和StringBuilder 对象中最后一个字符不相等
> 5.  将当前字符添加到 StringBuilder 对象中
> 6.  返回处理后的字符串

# 3. 代码 #

## 代码1： ##

class Solution {
        
        public String removeDuplicates(String s) {
        
            Stack<Character> stack = new Stack<>();  // 初始化一个栈
            for (char c : s.toCharArray()) {
          // 遍历字符串中的每个字符
                if (!stack.isEmpty() && stack.peek() == c) {
          // 如果栈不为空并且栈顶元素与当前字符相同，则弹出栈顶元素
                    stack.pop();
                } else {
          // 否则将当前字符压入栈中
                    stack.push(c);
                }
            }
            StringBuilder sb = new StringBuilder();
            for (char c : stack) {
          // 将栈中的元素转换成字符串
                sb.append(c);
            }
            return sb.toString();
        }
    }

> 解题思路基本相同，定义string，获得stack的索引元素拼接并返回

class Solution {
        
        public String removeDuplicates(String s) {
        
            Stack<Character> stack = new Stack<>();
            for(char c:s.toCharArray()){
        
                if(!stack.isEmpty()&&stack.peek()==c){
        
                    stack.pop();
                }else{
        
                    stack.push(c);
                }
            }
            StringBuilder sb = new StringBuilder();
            for(char c: stack){
        
                sb.append(c);
            }
            return sb.toString();
        }
    }

> 解题思路基本相同，把stack的栈顶元素弹出放入 StringBuilder，然后反转元素

public String removeDuplicates(String s) {
        
        Stack<Character> stack = new Stack();
        StringBuilder sb = new StringBuilder();
        // 遍历字符串中的每一个字符
        for(int i = 0; i < s.length(); i++) {
        
            // 如果栈不为空且栈顶元素和当前字符相同，则弹出栈顶元素
            if(!stack.isEmpty() && stack.peek() == s.charAt(i)){
        
                stack.pop();
            } else{
        
                // 否则将当前字符压入栈中
                stack.push(s.charAt(i));
            }
        }
        // 将栈中的元素倒序输出到 StringBuilder 中
        while(!stack.isEmpty()){
        
            sb.append(stack.pop());
        }
        // 返回字符串
        return sb.reverse().toString();
    }

## 代码2： ##

class Solution {
        
        public String removeDuplicates(String s) {
        
            StringBuilder sb = new StringBuilder(); // 创建 StringBuilder 对象
            for (char c : s.toCharArray()) {
         // 遍历字符串 s 的每个字符
                int length = sb.length(); // 记录当前 StringBuilder 对象的长度
                if (sb.length() != 0 && sb.charAt(length - 1) == c) {
         // 如果当前字符和 StringBuilder 对象中最后一个字符相等
                    sb.setLength(length - 1); // 删除 StringBuilder 对象中最后一个字符
                } else {
         // 如果当前字符和 StringBuilder 对象中最后一个字符不相等
                    sb.append(c); // 将当前字符添加到 StringBuilder 对象中
                }
            }
            return sb.toString(); // 返回处理后的字符串
        }
    }

> 解题思路基本相同,使用sb.deleteCharAt(sb.length()-1)的方法删除元素

class Solution {
        
        public String removeDuplicates(String s) {
        
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
        
                // 如果sb为空或者最后一个字符不等于当前字符，则直接加入sb中
                if(sb.length() == 0 || sb.charAt(sb.length()-1) != s.charAt(i)){
        
                    sb.append(s.charAt(i));
                } else {
         // 如果最后一个字符等于当前字符，则删除最后一个字符
                    sb.deleteCharAt(sb.length()-1);
                }
            }
            return sb.toString();
        }
    }