目录
删除字符中的所有相邻重复项（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();
}
}