java - Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character

Question

Example 1:

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".
Example 2:

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".
Example 3:

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".
Example 4:

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

class Solution {
    public boolean backspaceCompare(String S, String T) {

        Stack<Character> stack1 = new Stack<Character>();
        Stack<Character> stack2 = new Stack<Character>();
        for(int i=0;i<S.length();i++){


            if(S.charAt(i)!='#'){
            stack1.push(S.charAt(i));

        }else{
                    stack1.pop();
                }
        }
        for(int j =0;j<T.length();j++){

            if(T.charAt(j)!='#'){
            stack2.push(S.charAt(j));

        }else 
                stack2.pop();
        }

        if(stack1==stack2)
            return true;
        return false;
    }
}

my output is false and answer should be true why is this not working?

Answer 1

The first mistake is pushing all the characters on the stack outside of the if statement.

Also you should check if stack is empty before removing items from it. Otherwise EmptyStackException is thrown.

// stack1.push(S.charAt(i)); <-- remove this line
if (S.charAt(i)!='#') {
   stack1.push(S.charAt(i));
}else if (!stack1.isEmpty()) { // <-- add this check
   stack1.pop();
}

The second mistake is you can't use == to compare the contents of two stacks, use .equals method instead:

if(stack1.equals(stack2))