Leetcode Backspace String Compare
比较含退格的字符串(Backspace String Compare)
给定 S
和 T
两个字符串,当它们分别被输入到空白的文本编辑器后,判断二者是否相等,并返回结果。 #
代表退格字符。
注意:如果对空文本输入退格字符,文本继续为空。
示例 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;
}