比较含退格的字符串(Backspace String Compare)

给定 ST 两个字符串,当它们分别被输入到空白的文本编辑器后,判断二者是否相等,并返回结果。 # 代表退格字符。

注意:如果对空文本输入退格字符,文本继续为空。

示例 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 = "#a#c"
输出:true
解释:S 和 T 都会变成 “c”。

示例 4:

输入:S = "a#c", T = "b"
输出:false
解释:S 会变成 “c”,但 T 仍然是 “b”。

提示:

  • 1 <= S.length <= 200
  • 1 <= T.length <= 200
  • S 和 T 只含有小写字母以及字符 ‘#'。

进阶:

  • 你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗?

C语言版:

void process(char * result,const char* S){
    int len = strlen(S); 
    int j =0 ;
    for(int i =0;i<len;i++) {
        if(S[i] != '#'){
            result[j] = S[i];
            j++;
        } else {
            if (j>0){
                j--;
            }
        }
    } 
    result[j] = '\0'
}
bool backspaceCompare(char *S, char * T){
    int len_S = strlen(S);
    char result_S[len_S+1];
    process(result_S,S);

    int len_T = strlen(T);
    char result_T[len_T+1];
    process(result_T,T);

    return strcmp(result_S,result_T) == 0;

}

改进版:

char * process(const char* str){

    int len = strlen(str); 
    char * result = malloc(sizeof(char)*(len+1));
    int j =0 ;
    for(int i =0;i<len;i++) {
        if(str[i] != '#'){
            result[j] = str[i];
            j++;
        } else {
            if (j>0){
                j--;
            }
        }
    } 
    result[j] = '\0';
    return result;
}
bool backspaceCompare(char *S, char * T){
    return strcmp(process(S),process(T)) == 0;

}

这里有一个问题就是,我们malloc了,但是没有free,这不是一个好习惯,因此可以再次修改,就是下面的代码

free改进版:

char * process(const char* str){

    int len = strlen(str); 
    char * result = malloc(sizeof(char)*(len+1));
    int j =0 ;
    for(int i =0;i<len;i++) {
        if(str[i] != '#'){
            result[j] = str[i];
            j++;
        } else {
            if (j>0){
                j--;
            }
        }
    } 
    result[j] = '\0';
    return result;
}
bool backspaceCompare(char *S, char * T){
    char * result_S = process(S);
    char * result_T = process(T);
    bool flag = (strcmp(result_S,result_T)==0);
    free(result_S);
    free(result_T);

    return flag;
}

如何不用额外的空间呢?

void process(char* str){
    int len = strlen(str); 
    int j =0 ;
    for(int i =0;i<len;i++) {
        if(str[i] != '#'){
            str[j] = str[i];
            j++;
        } else {
            if (j>0){
                j--;
            }
        }
    } 
    str[j] = '\0';
}
bool backspaceCompare(char *S, char * T){
    process(S);
    process(T);
    bool flag = (strcmp(S,T)==0);
    return flag;
}

又或者

char * process(char* str){
    int len = strlen(str); 
    int j =0 ;
    for(int i =0;i<len;i++) {
        if(str[i] != '#'){
            str[j] = str[i];
            j++;
        } else {
            if (j>0){
                j--;
            }
        }
    } 
    str[j] = '\0';
    return str;
}
bool backspaceCompare(char *S, char * T){
    return strcmp(process(S),process(T))==0;
}