当前位置 博文首页 > 冢狐的私人空间：日拱一卒——LeetCode 844.比较含退格的字符串
大家好呀，今天为大家带来的LeetCode的题目是LeetCode 844.比较含退格的字符串。算是一道比较基础的题目。
这道题目相对简单，主要就是将时间复杂度和空间复杂度降低下来。
最简单的思路，就是按照题目的描述，将这两个字符串变为一般形式，然后直接比较是否相等即可。
由于一个字符是否存活要取决于后面是否有退格符，所以我们只需要要逆序遍历字符串，然后就可以得到一般字符串然后比较是否相等。
public boolean backspaceCompare(String S, String T) {
return build(S).equals(build(T));
}
public String build (String str){
StringBuffer ans = new StringBuffer();
int length = str.length();
for(int i=0;i<length;i++){
if(str.charAt(i)=='#'){
if(ans.length()>0)
ans.deleteCharAt(ans.length()-1);
}else{
ans.append(str.charAt(i));
}
}
return ans.toString();
}
public boolean backspaceCompare(String S, String T) {
int i = S.length() - 1, j = T.length() - 1;
int skipS = 0, skipT = 0;
while (i >= 0 || j >= 0) {
while (i >= 0) {
if (S.charAt(i) == '#') {
skipS++;
i--;
} else if (skipS > 0) {
skipS--;
i--;
} else {
break;
}
}
while (j >= 0) {
if (T.charAt(j) == '#') {
skipT++;
j--;
} else if (skipT > 0) {
skipT--;
j--;
} else {
break;
}
}
if (i >= 0 && j >= 0) {
if (S.charAt(i) != T.charAt(j)) {
return false;
}
} else {
if (i >= 0 || j >= 0) {
return false;
}
}
i--;
j--;
}
return true;
}
