描述

1047. 删除字符串中的所有相邻重复项 - 力扣（Leetcode）

分析

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.Scanner;
import java.util.Deque;

//1047. 删除字符串中的所有相邻重复项
public class RemoveAllAdjacentDuplicatesInString1047 {
	public static void main(String[] args) {
		System.out.println(new Solution().removeDuplicates(new Scanner(System.in).nextLine()));
	}
}
//栈法
class Solution {
    public String removeDuplicates(String s) {
    	ArrayDeque<Character> res = new ArrayDeque<>();
    	for(char item : s.toCharArray()){
    		if (res.isEmpty() || item != res.peek()) {
    			res.push(item);
    		}else{
    			res.pop();
    		}
    	}

    	String r = "";
    	while(!res.isEmpty()){
    		r = res.pop() + r;
    	}
    	return r;
    }
}
//双指针法
class Solution {
    public String removeDuplicates(String s) {
    	int slow = 0, fast = 0;
    	char[] res = s.toCharArray();
    	while(fast < s.length()){
    		res[slow] = res[fast];
    		if (slow > 0 && res[slow] == res[slow - 1]) {
    			slow--;
    		}else{
    			slow++;
    		}
    		fast++;
    	}	
    	return new String(res, 0, slow);
    }
}

总结

以后用双指针法，更加高效。