题目大意
给定 S 和 T 两个字符串,当它们分别被输入到空白的文本编辑器后,判断二者是否相等,并返回结果。 # 代表退格字符。
注意:如果对空文本输入退格字符,文本继续为空。
示例1:
输入:S = "ab#c", T = "ad#c"
输出:true
解释:S 和 T 都会变成 “ac”。
示例2:
输入:S = "ab##", T = "c#d#"
输出:true
解释:S 和 T 都会变成 “”。
代码一:数组代替栈
遇到'#'就pop,最后比较两个栈中的元素是否完全相同。
public boolean backspaceCompare(String S, String T) {
char[] s = new char[S.length()];
char[] t = new char[T.length()];
int i=0,j=0;
for(char v:S.toCharArray()) {
if(v == '#') {
i = i-1 < 0? 0:i-1;
s[i] = '\0';
} else {
s[i] = v;
++i;
}
}
for(char v:T.toCharArray()) {
if(v == '#') {
j = j-1 < 0? 0:j-1;
t[j] = '\0';
} else {
t[j] = v;
++j;
}
}
if(i!=j) return false;
for(int k=0;k<i;k++)
if(s[k]!=t[k]) return false;
return true;
}
运行时间1ms,击败97.63%。
代码二:双指针
从末尾开始扫描字符串。一个字符能否出现,取决于它右边的‘#’的个数。
public boolean backspaceCompare(String S, String T) {
int skipS = 0, skipT = 0; //跳过的字符个数
int i = S.length()-1, j = T.length()-1; //从字符串末尾开始遍历
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)) return false;
if(i>=0 && j>=0 && S.charAt(i) != T.charAt(j)) return false;
--i;--j;
}
return true;
}