转载自Leet
Code
题目描述
给出由小写字母组成的字符串S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在S上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例： >输入："abbaca" >输出："ca"
>解释：
>例如，在"abbaca"中，我们可以删除"bb"由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串"aaca"，其中又只有"aa"可以执行重复项删除操作，所以最后的字符串为"ca"。
提示：
- `1 <= S.length <= 20000``
- `
S仅由小写英文字母组成。
我的代码
\(T(N) = O(N)\), \(S(N) = O(N)\)
{.line-numbers}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class MySolution1047
{
Stack<Character> stack = new Stack();
public String removeDuplicates(String S)
{
String ans = "";
for (char ch:S.toCharArray())
{
if (stack.isEmpty()||stack.peek()!=ch)
stack.push(ch);
else
while (!stack.isEmpty()&&stack.peek()==ch)
stack.pop();
}
char []arr = new char[stack.size()];
for (int i=stack.size()-1; i>=0; i--)
arr[i]=stack.pop();
for (char ch:arr)
ans+=ch;
return ans;
}
}
|
思路:StringBuilder
\(T(N) = O(N)\), \(S(N) = O(N)\)
代码
{.line-numbers}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution1047
{
public String removeDuplicates(String S)
{
StringBuilder sb = new StringBuilder();
int sbLength = 0;
for (char ch : S.toCharArray())
{
if (sbLength != 0 && ch == sb.charAt(sbLength - 1))
sb.deleteCharAt(sbLength-- - 1);
else
{
sb.append(ch);
sbLength++;
}
}
return sb.toString();
}
}
|
