【字符串】比较含退格的字符

思路：双指针

1.先将两个字符串转换为无"#"字符串，再进行比较（用双指针实现）：

1.若fast!='#'，则将fast值赋给slow，两指针均后移

2.否则slow指针前移一位，fast指针后移一位

2.实现函数对比两字符串

void convertString(char* str) {
    int fast = 0;
    int slow = 0;
    while(str[fast] != '\\0') {
        if(str[fast] != '#') {
            str[slow++] = str[fast];
        } else {
            slow--;
            slow = slow >= 0 ? slow : 0;
        }
        fast++;
    }
    str[slow] = '\\0';
}

bool backspaceCompare(char * s, char * t){
    convertString(s);
    convertString(t);
    return strcmp(s,t) == 0;
}

官方思路一：用栈处理

遍历每个字符：

• 若它是退格符，则出栈栈顶的一个元素
• 若是普通字符，则入栈
• 最后返回栈

char* convertString(char* str) {
    int length = strlen(str);
    int i = 0;
    char* ret = (char*)malloc(sizeof(char)*(length+1));
    int count = 0;
    for(i = 0; i < length; i++) {
        if(str[i] != '#') {
            ret[count++] = str[i];
        } else if(count > 0) 
            count--;
    }
    ret[count] = '\\0';
    return ret;
}

bool backspaceCompare(char * s, char * t){
    return strcmp(convertString(s),convertString(t)) == 0;
}

官方思路2：

一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。

具体地，我们定义 skip表示当前待删除的字符的数量。每次我们遍历到一个字符：

• 若该字符为退格符，则我们需要多删除一个普通字符，我们让skip加 1；
• 若该字符为普通字符：
  • 若 skip 为 0，则说明当前字符不需要删去；
  • 若skip 不为 0，则说明当前字符需要删去，我们让skip减 1。