-
Notifications
You must be signed in to change notification settings - Fork 8
/
RemoveAllAdjacentDuplicatesInString.java
51 lines (48 loc) · 1.34 KB
/
RemoveAllAdjacentDuplicatesInString.java
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
46
47
48
49
50
51
package stack;
// Source : https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/
// Id : 1047
// Author : Fanlu Hai | https://github.com/Fanlu91/FanluLeetcode
// Date : 2022/2/9
// Topic : stack
// Level : Easy
// Other :
// Tips :
// Links :
// Result : 100.00% 16.48%
import java.util.Deque;
import java.util.LinkedList;
public class RemoveAllAdjacentDuplicatesInString {
// 19 ms
public String removeDuplicates(String s) {
Deque<Character> stack = new LinkedList<>();
char[] arr = s.toCharArray();
for (int i = 0; i < s.length(); i++) {
if (stack.isEmpty() || arr[i] != stack.peek())
stack.push(arr[i]);
else
stack.pop();
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty())
sb.append(stack.pollLast());
return sb.toString();
}
// 3ms
public String removeDuplicates1(String S) {
// public String removeDuplicates(String S) {
char[] s = S.toCharArray();
int i = -1;
for (char c : s) {
if (i == -1) {
s[++i] = c;
continue;
}
if (s[i] == c) {
i--;
} else {
s[++i] = c;
}
}
return String.valueOf(s, 0, i + 1);
}
}