给定 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 <= 2001 <= T.length <= 200-
S和T只含有小写字母以及字符'#'。
class Solution {
public boolean backspaceCompare(String S, String T) {
Stack<Character> stacks = new Stack<Character>();
Stack<Character> stackt = new Stack<Character>();
for(int i = 0;i < S.length();i++){
if(S.charAt(i)=='#' && !stacks.isEmpty()){
stacks.pop();
continue;
}else if(S.charAt(i) != '#'){
stacks.push(S.charAt(i));
}
}
for(int j = 0;j < T.length();j++){
if(T.charAt(j)=='#' && !stackt.isEmpty()){
stackt.pop();
continue;
}else if(T.charAt(j) != '#'){
stackt.push(T.charAt(j));
}
}
while(!stacks.isEmpty()&&!stackt.isEmpty()){
if(stacks.pop()!=stackt.pop()){
//System.out.println("1");
return false;
}
}
if((stacks.isEmpty() && !stackt.isEmpty() )||(!stacks.isEmpty() && stackt.isEmpty() )){
//System.out.println("2");
return false;
}
return true;
}
}
官方大佬：
class Solution {
public boolean backspaceCompare(String S, String T) {
char[] stack1 = new char[S.length()];
char[] stack2 = new char[T.length()];
int top1 = 0;
for(int i = 0; i < S.length(); i++){
if(S.charAt(i) != '#')
stack1[top1++] = S.charAt(i);
else if(top1 > 0)
top1--;
}
int top2 = 0;
for(int i = 0; i < T.length(); i++){
if(T.charAt(i) != '#')
stack2[top2++] = T.charAt(i);
else if(top2 > 0)
top2--;
}
if(top1 != top2)
return false;
for(int i = 0; i < top1; i++){
if(stack1[i] != stack2[i])
return false;
}
return true;
}
}
2019-03-08 11:10:32