该题是LeetCode第137次周赛的编号为1047的题目,三周前的一次周赛,其实我都已经忘了题目了...毫无印象三周前我也参加了周赛。
这好像是系列的第一个周赛题,每次参加的周赛,都由于实力有限,所以都只写了一两题的Easy的题目....之后慢慢努力完成Medium的吧。
原题地址: https://leetcode-cn.com/contest/weekly-contest-137/problems/remove-all-adjacent-duplicates-in-string/
题目描述:
给出由小写字母组成的字符串 S
,重复项删除操作会选择两个相邻且相同的字母,并删除它们。
在 S 上反复执行重复项删除操作,直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例:
输入:"abbaca"
输出:"ca"
解释:
例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。
提示:
1 <= S.length <= 20000
S
仅由小写英文字母组成。解题思路:
关于这题,我的思路是用暴力法解决问题,简单易懂,同时效率也不高。
首先将输入的字符串包装为StringBuilder对象,然后一直从头遍历StringBuilder对象,找到重复字符串,就把这两个重复的给删除,删除之后,再从头遍历该StringBuilder对象,直到遍历StringBuilder之后发现不了重复字符为止。最后返回该StringBuilder对象。
后来意识到,可以使用栈的方式解决该问题,只需要遍历一次就可以解决问题,内存占用也少很多。
中文题解:
https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/solution/
个人题解:
public String removeDuplicates(String S) {
StringBuilder stringBuilder = new StringBuilder(S);
while (true) {
boolean flag = false;
for (int i = 0; i < stringBuilder.length() - 1; i++) {
if (stringBuilder.charAt(i) == stringBuilder.charAt(i + 1)) {
stringBuilder.deleteCharAt(i);
stringBuilder.deleteCharAt(i);
i = -1;
flag = true;
}
}
if (!flag) {
return stringBuilder.toString();
}
}
}
结果:
错误示范下的运行结果,可以看到结果相当的理想,只超越了12%的人,还好不是垫底。