比較含退格的字元串

給定 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. 1 <= S.length <= 200
2. 1 <= T.length <= 200
3. S 和 T 只含有小寫字母以及字元 '#'

根據這一題，掌握數據結構中棧的使用

題目分析：

題目的意思是，在兩個字元串中，對於每一個字元串，如果存在'#'符號，並且它前面有字元，則刪除它前面的字元，'#'號也刪除；如果'#'前面沒有字元，則只刪除'#'號；之後再比較兩個字元串是不是相等（即剩餘的元素相同）。

很明顯，此題可以使用棧的知識解決：掃描每一個字元串，當讀到的字元串中的字元不是'#'的時候，字元入棧；當讀到'#'的時候，如果棧不為空（很重要，千萬別忘記判斷，如果不進行棧空的判斷，當棧空的時候如果進行pop()操作則會報錯）的時候，刪除棧頂元素；最後對比兩個字元串是不是相等。

剛開始，我使用兩個棧來進行操作，可以看出要進行兩個for迴圈操作：

 1 class Solution {
 2    public boolean backspaceCompare(String S, String T)
 3     {
 4         Stack<Character> stack1 = new Stack<>();
 5         Stack<Character> stack2 = new Stack<>();
 6 
 7         for (char c : S.toCharArray())
 8         {
 9             if (c != '#')
10                 stack1.push(c);
11             else
12             {
13                 if (!stack1.isEmpty())
14                     stack1.pop();
15             }
16         }
17 
18         for (char c : T.toCharArray())
19         {
20             if (c != '#')
21                 stack2.push(c);
22             else
23             {
24                 if (!stack2.isEmpty())
25                     stack2.pop();
26             }
27         }
28 
29         return stack1.equals(stack2);
30     }
31 }

之後我選擇使用JAVA泛型，將方法抽象出來，只使用了一次for迴圈，減少了代碼量：

 1 class Solution {
 2     public boolean backspaceCompare(String S, String T)
 3     {
 4         return compute(S).equals(compute(T));
 5     }
 6 
 7     private Stack<Character> compute(String s)
 8     {
 9         Stack<Character> stack = new Stack<>();
10 
11         for (char c : s.toCharArray())
12         {
13             if (c != '#')
14                 stack.push(c);
15             else
16             {
17                 if (!stack.isEmpty())
18                     stack.pop();
19             }
20         }
21 
22         return stack;
23     }
24 }

主函數：

 1 public static void main(String[] args)
 2     {
 3         T8 t = new T8();
 4 
 5         String S1 = "a##b";
 6         String T1 = "#a#b";
 7         System.out.println(t.backspaceCompare(S1, T1));
 8 
 9         String S2 = "a#c";
10         String T2 = "b";
11         System.out.println(t.backspaceCompare(S2, T2));
12 
13     }

運行結果：

1 true
2 false