1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public String removeDuplicates(String s) {
char[] sArray = s.toCharArray();
int left = 0, right = 1;
while (right < sArray.length) {
if (left != -1 && sArray[left] == sArray[right]) {
left -= 1;
} else {
sArray[left + 1] = sArray[right];
left += 1;
}
right += 1;
}
StringBuilder ans = new StringBuilder();
for (int i = 0; i <= left; i++) {
ans.append(sArray[i]);
}
return ans.toString();
}
}
|
two pointers.
时间复杂度: O(n)
空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public String removeDuplicates(String s) {
StringBuilder ans = new StringBuilder();
int length = 0;
for (int i = 0; i < s.length(); i++) {
if (length != 0 && ans.charAt(length - 1) == s.charAt(i)) {
ans.deleteCharAt(length - 1);
length -= 1;
} else {
ans.append(s.charAt(i));
length += 1;
}
}
return ans.toString();
}
}
|
这个的话更加简洁. 用StringBuilder充当stack.
时间复杂度: O(n)
空间复杂度: O(n - d) d是所有duplicates的长度加在一起(也就是被抵消的duplicates加在一起)
