【优选算法】（第三十三篇）
目录
删除字符中的所有相邻重复项（easy）
题目解析
讲解算法原理
编写代码
⽐较含退格的字符串（easy）
题目解析
讲解算法原理
编写代码
删除字符中的所有相邻重复项（easy）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给出由⼩写字⺟组成的字符串S，重复项删除操作会选择两个相邻且相同的字⺟，并删除它们。在S上反复执⾏重复项删除操作，直到⽆法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯⼀。
⽰例：
输⼊："abbaca"
输出："ca"
解释：
例如，在"abbaca"中，我们可以删除"bb"由于两字⺟相邻且相同，这是此时唯⼀可以执⾏删除操作的重复项。之后我们得到字符串"aaca"，其中⼜只有"aa"可以执⾏重复项删除操作，所以最后的字符串为"ca"。
讲解算法原理
解法（栈）：
算法思路：
本题极像我们玩过的「开⼼消消乐」游戏，仔细观察消除过程，可以发现本题与我们之前做过的「括号匹配」问题是类似的。当前元素是否被消除，需要知道上⼀个元素的信息，因此可以⽤「栈」来保存信息。
但是，如果使⽤ stack 来保存的话，最后还需要把结果从栈中取出来。不如直接⽤「数组模拟⼀个栈」结构：在数组的尾部「尾插尾删」，实现栈的「进栈」和「出栈」。那么最后数组存留的内容，就是最后的结果。
编写代码
c++算法代码：
class Solution
{
public:string removeDuplicates(string s) {string ret; // 搞⼀个数组，模拟栈结构即可for(auto ch : s){if(ret.size() && ch == ret.back()) ret.pop_back(); // 出栈 else ret += ch; // ⼊栈}return ret;}
};java算法代码：
class Solution
{public String removeDuplicates(String _s) {StringBuffer ret = new StringBuffer(); // ⽤数组来模拟栈结构 char[] s = _s.toCharArray();for(char ch : s){if(ret.length() > 0 && ch == ret.charAt(ret.length() - 1)){// 出栈ret.deleteCharAt(ret.length() - 1);}else{// 进栈ret.append(ch);}}return ret.toString();}
}⽐较含退格的字符串（easy）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给定s和t两个字符串，当它们分别被输⼊到空⽩的⽂本编辑器后，如果两者相等，返回true。#代表退格字符。
注意：如果对空⽂本输⼊退格字符，⽂本继续为空。
⽰例1：
输⼊：s="ab#c",t="ad#c"
输出：true
解释：
s和t都会变成"ac"。
⽰例2：
输⼊：s="ab##",t="c#d#"
输出：true
解释：
s和t都会变成""。
讲解算法原理
解法（⽤数组模拟栈）：
算法思路：
由于退格的时候需要知道「前⾯元素」的信息，⽽且退格也符合「后进先出」的特性。因此我们可以使⽤「栈」结构来模拟退格的过程。
• 当遇到⾮ # 字符的时候，直接进栈；
• 当遇到 # 的时候，栈顶元素出栈。
为了⽅便统计结果，我们使⽤「数组」来模拟实现栈结构。
编写代码
c++算法代码：
class Solution
{
public:bool backspaceCompare(string s, string t) {return changeStr(s) == changeStr(t);}string changeStr(string& s){string ret; // ⽤数组模拟栈结构for(char ch : s){if(ch != '#') ret += ch;else{if(ret.size()) ret.pop_back();}}return ret;}
};java算法代码：
class Solution
{public boolean backspaceCompare(String s, String t) {return changeStr(s).equals(changeStr(t));}public String changeStr(String s){StringBuffer ret = new StringBuffer(); // ⽤数组模拟栈结构for(int i = 0; i < s.length(); i++){char ch = s.charAt(i);if(ch != '#'){ret.append(ch); // ⼊栈}else{if(ret.length() > 0) ret.deleteCharAt(ret.length() - 1); // 出栈 }}return ret.toString();}
}