题目:给定 s 和 t 两个字符串,当它们分别被输入到空白的文本编辑器后,如果两者相等,返回 true 。# 代表退格字符。 注意:如果对空文本输入退格字符,文本继续为空。
示例 1: 输入:s = “ab#c”, t = “ad#c” 输出:true 解释:s 和 t 都会变成 “ac”。
示例 2: 输入:s = “ab##”, t = “c#d#” 输出:true 解释:s 和 t 都会变成 “”。
示例 3: 输入:s = “a#c”, t = “b” 输出:false 解释:s 会变成 “c”,但 t 仍然是 “b”。
提示: 1 <= s.length, t.length <= 200 s 和 t 只含有小写字母以及字符 ‘#’
思路:创建两个栈分别存放 s 字符串和 t 字符串的有效字符,如果是退格符,就出栈;否则入栈;最后比较两个栈是否相同;
bool backspaceCompare(char* s, char* t)
{
// 创建 s 字符串和 t 字符串的栈,存放有效的字符
char stackS[201] = "\0";
char stackT[201] = "\0";
//topS 和 topT 记录栈顶
int topS = 0, topT = 0;
for (int i = 0; i < strlen(s); i++)
{
//如果是退格符,并且不是第一个字符,就出栈,并补个'\0'
if (s[i] == '#')
{
if (topS)
{
topS--;
stackS[topS] = '\0';
}
}
//否则,就入栈
else
{
stackS[topS++] = s[i];
}
}
//同理,栈T也和栈S一样
for (int i = 0; i < strlen(t); i++)
{
if (t[i] == '#')
{
if (topT)
{
topT--;
stackT[topT] = '\0';
}
}
else
{
stackT[topT++] = t[i];
}
}
//最后比较栈S和栈T是否相同
return (bool)!strcmp(stackS, stackT);
}
题目:给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。
在 S 上反复执行重复项删除操作,直到无法继续删除。 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例: 输入:“abbaca” 输出:“ca” 解释: 例如,在 “abbaca” 中,我们可以删除 “bb” 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”,其中又只有 “aa” 可以执行重复项删除操作,所以最后的字符串为 “ca”。
提示: 1 <= S.length <= 20000 S 仅由小写英文字母组成。
思路:开辟一个栈,大小为 s 字符串的长度加一;如果是第一个位置或者栈顶元素不等于当前字符串的字符,就入栈;否则就出栈,并补上’\0’;在最后也要补上’ \0 ';
char* removeDuplicates(char* s)
{
//开辟 s 字符串长度加一的空间大小
char* Stack = (char*)malloc(sizeof(char) * (strlen(s) + 1));
//pos为当前栈的位置
int pos = 0;
//遍历字符串
for (int i = 0; i < strlen(s); i++)
{
//如果是第一个位置或者栈顶元素不等于当前字符,就入栈
if (pos == 0 || Stack[pos - 1] != s[i])
{
Stack[pos++] = s[i];
}
//否则,就出栈,并补上'\0'
else
{
pos--;
Stack[pos] = '\0';
}
}
//在最后加上'\0'
Stack[pos] = '\0';
return Stack;
}