# 题目
给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。
在 S 上反复执行重复项删除操作,直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例:
- 输入:"abbaca"
- 输出:"ca"
- 解释:例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。
提示:
- 1 <= S.length <= 20000
- S 仅由小写英文字母组成。
1047. 删除字符串中的所有相邻重复项 - 力扣(LeetCode)
# 分析
这道题其实也是匹配问题,匹配相邻元素,重复即消除,用栈来实现
遍历字符串入栈,并与栈顶元素判断是否相等,相等继续下一个元素并且栈顶 pop,不相等入栈,最后把栈元素都出栈反转成字符串
// 时间复杂度: O (n) | |
// 空间复杂度: O (n) | |
class Solution { | |
public: | |
string removeDuplicates(string S) { | |
stack<char> st; | |
for (char s : S) { | |
if (st.empty() || s != st.top()) { | |
st.push(s); | |
} else { | |
st.pop(); //s 与 st.top () 相等的情况 | |
} | |
} | |
string result = ""; | |
while (!st.empty()) { // 将栈中元素放到 result 字符串汇总 | |
result += st.top(); | |
st.pop(); | |
} | |
reverse (result.begin(), result.end()); // 此时字符串需要反转一下 | |
return result; | |
} | |
}; |