LeetCode--844--比较含退格的字符串（java）

给定 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 只含有小写字母以及字符 '#'。

 1 class Solution {
 2     public boolean backspaceCompare(String S, String T) {
 3         Stack<Character> stacks = new Stack<Character>();
 4         Stack<Character> stackt = new Stack<Character>();
 5         for(int i  = 0;i < S.length();i++){
 6             if(S.charAt(i)=='#' && !stacks.isEmpty()){
 7                 stacks.pop();
 8                 continue;
 9             }else if(S.charAt(i) != '#'){
10                 stacks.push(S.charAt(i));
11             }
12             
13         }
14         for(int j  = 0;j < T.length();j++){
15             if(T.charAt(j)=='#' && !stackt.isEmpty()){
16                 stackt.pop();
17                 continue;
18             }else if(T.charAt(j) != '#'){
19                 stackt.push(T.charAt(j));
20             }
21         }
22         while(!stacks.isEmpty()&&!stackt.isEmpty()){
23             if(stacks.pop()!=stackt.pop()){
24                 //System.out.println("1");
25                 return false;
26             }
27         }
28         
29         if((stacks.isEmpty() && !stackt.isEmpty() )||(!stacks.isEmpty() && stackt.isEmpty() )){
30             //System.out.println("2");
31             return false;
32         }
33         return true;
34     }
35 }

官方大佬：

 1 class Solution {
 2     public boolean backspaceCompare(String S, String T) {
 3         char[] stack1 = new char[S.length()];
 4         char[] stack2 = new char[T.length()];
 5         int top1 = 0;
 6         for(int i = 0; i < S.length(); i++){
 7             if(S.charAt(i) != '#')
 8                 stack1[top1++] = S.charAt(i);
 9             else if(top1 > 0)
10                 top1--;
11         }
12         int top2 = 0;
13         for(int i = 0; i < T.length(); i++){
14             if(T.charAt(i) != '#')
15                 stack2[top2++] = T.charAt(i);
16             else if(top2 > 0)
17                 top2--;
18         }
19         if(top1 != top2)
20             return false;
21         for(int i = 0; i < top1; i++){
22             if(stack1[i] != stack2[i])
23                 return false;
24         }
25         return true;
26     }
27 }

2019-03-08 11:10:32