https://leetcode.cn/problems/backspace-string-compare/description/
一、题目描述
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
二、相关知识点了解
今天要做的这道题目用到的算法，在前几期都有用到过，叫做双指针法，这里就不过多的介绍了，不了解的小伙伴可以点击链接了解一下！
https://blog.csdn.net/m0_75144071/article/details/144771622?spm=1001.2014.3001.5501
https://blog.csdn.net/m0_75144071/article/details/143021601?spm=1001.2014.3001.5502
两个题目的难度都不大，看完今天的题解可以自行挑战一下哦！
三、示例分析
示例 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"。
这里说明了给出两个字符串，其中的‘#’代表退格也就是咱们键盘上的删除键（Backspace），并将其最终的结果进行比对，如果相同返回true，否则返回false。还是比较容易理解的。
四、解题思路&代码实现
按照上述的分析，我们可以直接利用一个简单粗暴的方式来实现这段代码。（其中的算法在相关知识点中有解释）就是双指针法。
我们可以想一下，无非就是不是‘#“号的字符我们留下，是”#’号的字符我们不要。
接下来正式开始今天的代码实现！
bool backspaceCompare(char* s, char* t) {
int len_s = strlen(s);
// 创建一个字符数组 ret_s 用于存储处理后的字符串 s，其大小为 len_s + 1，以容纳字符串结束符 '\0'
char ret_s[len_s + 1];
int j = 0;
// 遍历字符串 s
for (int i = 0; i < len_s; i++) {
// 如果当前字符不是 '#'
if (s[i]!= '#') {
// 将当前字符存入 ret_s 数组，并将 j 指针后移一位
ret_s[j++] = s[i];
} else {
// 如果当前字符是 '#'，且 j 大于 0（即 ret_s 数组中已有字符）
if (j > 0) {
// 将 j 指针回退一位，模拟退格操作
j--;
}
}
}
// 在处理后的字符串 ret_s 末尾添加字符串结束符 '\0'
ret_s[j] = '\0';
}这里我们选择先对其中一个字符串进行上述的处理，下一个字符串也同样是这样做。（这里就不再添加注释了，和上述代码进行的操作相同）
bool backspaceCompare(char* s, char* t) {
int len_s = strlen(s);
// 创建一个字符数组 ret_s 用于存储处理后的字符串 s，其大小为 len_s + 1，以容纳字符串结束符 '\0'
char ret_s[len_s + 1];
int j = 0;
// 遍历字符串 s
for (int i = 0; i < len_s; i++) {
// 如果当前字符不是 '#'
if (s[i]!= '#') {
// 将当前字符存入 ret_s 数组，并将 j 指针后移一位
ret_s[j++] = s[i];
} else {
// 如果当前字符是 '#'，且 j 大于 0（即 ret_s 数组中已有字符）
if (j > 0) {
// 将 j 指针回退一位，模拟退格操作
j--;
}
}
}
// 在处理后的字符串 ret_s 末尾添加字符串结束符 '\0'
ret_s[j] = '\0';
int len_t = strlen(t);
char ret_t[len_t+1];
j = 0;
for (int i = 0; i < len_t; i++) {
if (t[i] != '#') {
ret_t[j++] = t[i];
} else {
if (j > 0) {
j--;
}
}
}
ret_t[j]='\0';
return strcmp(ret_s,ret_t)==0;
}整体的思路就是开辟出一个新的空间用来存放处理后的结果，与另一个结果进行比对。
但是！在几乎任何的编译语言中都不希望代码出现冗余（也就是重复的部分），我们可以将这段重复的代码，进行封装，使其称为一个独立的函数。在我们需要的时候进行调用即可！
char* result(char* src) {
// 计算源字符串的长度，并加上1（为字符串结束符'\0'预留空间）
int len = strlen(src) + 1;
// 动态分配内存，用于存储处理后的字符串
// 分配的大小为字符指针大小乘以（长度 + 1）
// 这里应该是 sizeof(char) * (len)，原代码 sizeof(char*) 是错误的
char* dst = (char*)malloc(sizeof(char) * len);
if (dst == NULL) {
// 如果内存分配失败，返回 NULL
return NULL;
}
int j = 0;
// 遍历源字符串
for (int i = 0; i < len - 1; i++) {
// 如果当前字符不是'#'
if (src[i]!= '#') {
// 将当前字符存入目标字符串，并将目标字符串索引j后移一位
dst[j++] = src[i];
} else {
// 如果当前字符是'#'，且目标字符串已有字符（j > 0）
if (j > 0) {
// 将目标字符串索引j回退一位，模拟退格操作
j--;
}
}
}
// 在处理后的字符串末尾添加字符串结束符'\0'
dst[j] = '\0';
// 返回处理后的字符串指针
return dst;
}
bool backspaceCompare(char* s, char* t) {
// 对字符串s进行处理，得到处理后的字符串
char* ret_s = result(s);
// 对字符串t进行处理，得到处理后的字符串
char* ret_t = result(t);
// 比较两个处理后的字符串是否相等
bool flag = strcmp(ret_s, ret_t) == 0;
// 释放动态分配的内存，避免内存泄漏
free(ret_s);
free(ret_t);
// 返回比较结果
return flag;
}由于这里需要将处理好的字符串进行回传，所以我们需要用malloc在堆区开辟空间。（注意：使用malloc开辟出的空间，在使用完毕后一定要记得使用free释放掉，避免造成内存泄露。希望大家养成良好的编程习惯）
五、代码优化
其实上述代码有一定的缺陷，它的空间复杂度为O(N)，我们其实完全可以在原地进行对字符串的处理将空间复杂度降低至O(1)，而不去选择开辟出一段新的内存空间。可以将其优化成这样
char* result(char* str) {
// 计算源字符串的长度
int len = strlen(str);
int j = 0;
// 遍历源字符串
for (int i = 0; i < len; i++) {
// 如果当前字符不是'#'
if (str[i]!= '#') {
// 将当前字符复制到新的位置（实际上是覆盖原字符串前面的部分）
str[j++] = str[i];
} else {
// 如果当前字符是'#'，且j大于0（表示前面已经有非'#'字符）
if (j > 0) {
// 将j回退一位，模拟退格操作
j--;
}
}
}
// 在处理后的字符串末尾添加字符串结束符'\0'
str[j] = '\0';
// 返回处理后的字符串指针
return str;
}
bool backspaceCompare(char* s, char* t) {
// 分别对字符串s和t进行处理，然后比较处理后的结果
return strcmp(result(s), result(t)) == 0;
}因为这里是直接对源字符串所在的内存空间上进行处理，所以不需要手动开辟空间，直接回传即可！
六、题目总结
- 本题通过含‘#’号退格字符进行比较，这一问题考验对字符操作和逻辑判断的掌握。
- 双指针法无疑是本题解决问题的关键，希望大家熟练掌握。
- 我们在遇见一个题目时，可以先在脑子里形成一段“伪代码”，之后按照这个思路，一步步的进行代码优化（时间复杂度或空间复杂度上）。
- 在使用malloc时，务必要记得在使用完毕以后，手动释放掉开辟出的内存，避免造成内存泄露。
通过这道含退格字符串比较题，深入探索了字符串处理细节与双指针算法精妙之处，从基础的字符判断、指针操作，到复杂的逻辑构建、性能优化，全方位提升编程思维。未来面对类似复杂字符串情境，无论是文本编辑模拟、数据格式清理，都能借鉴本题思路，灵活运用双指针、合理管理内存，写出更高效、健壮的代码，向着编程高手之路稳步迈进。谢谢大家！荆轲刺秦！！！
标签：字符,Day9,int,ret,char,C++,len,字符串,退格 From： https://blog.csdn.net/m0_75144071/article/details/144850188