(题目来源:力扣LeetCode)
题目:给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。
在 S 上反复执行重复项删除操作,直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
题解:
解决方法:栈
分析题目:1)两个相邻相同的字符会被删除
2)删除两个相邻的字符又可能会产生新的相邻且相同的字符
根据以上两点联想到:栈——后进先出的特性,通过栈来缓存结果,只需要遍历字符串一次就能解决本题。
从左到右一次遍历字符串的字符Si,并将每次遍历的的Si与栈顶元素比较:1、如果相等,则将栈顶弹出 2、如果不等Si元素入栈,向后继续遍历。
class Solution {
public String removeDuplicates(String S) {
//定义数据结构————栈,用来缓存结果
Stack<Character> stack =new Stack<>();
for(int i=0;i<S.length();i++){
//如果栈不为空,字符串的第i个元素等于栈顶元素,就将栈顶弹出
if(!stack.empty()&& S.charAt(i)==stack.peek()){
stack.pop();
}else{
stack.add(S.charAt(i));
}
}
//优化数据
StringBuilder str=new StringBuilder();
for(Character c:stack){
str.append(c);
}
return str.toString();
}
}