给定 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
     
       stack1 = new Stack<>(); 5         Stack
      
        stack2 = new Stack<>(); 6  7         for (char c : S.toCharArray()) 8         { 9             if (c != '#')10                 stack1.push(c);11             else12             {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             else23             {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
     
       compute(String s) 8     { 9         Stack
      
        stack = new Stack<>();10 11         for (char c : s.toCharArray())12         {13             if (c != '#')14                 stack.push(c);15             else16             {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 true2 false