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

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?

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))

Answer by Joni correctly addresses the errors in the code, however there are some other issues I'd like to address:

• You should use a helper method to eliminate repeating the same code.

• You should use Deque instead of Stack. The javadoc says so.

• Instead of using Stack/Deque, I'd recommend using StringBuilder, to prevent having to box the char values.

Something like this:

public boolean backspaceCompare(String s, String t) {
	return applyBackspace(s).equals(applyBackspace(t));
}

private static String applyBackspace(String s) {
	StringBuilder buf = new StringBuilder();
	for (int i = 0; i < s.length(); i++) {
		if (s.charAt(i) != '#')
			buf.append(s.charAt(i));
		else if (buf.length() != 0)
			buf.setLength(buf.length() - 1);
	}
	return buf.toString();
}

Your idea works, but it's expensive and unnecessary to copy the strings into stacks. If you work backwards from the end, no extra storage is necessary:

//given the string length or a valid character position, return
//the position of the previous valid character, or -1 if none
public static int previousCharPos(String s, int pos)
{
	int bs=0; // number of backspaces to match
	while(pos>0) {
		--pos;
		if (s.charAt(pos)=='#') {
			++bs;
		} else if (bs <= 0) {
			return pos;
		} else {
			--bs;
		}
	}
	return -1;
}

public static boolean backspaceCompare(String S, String T)
{
	int spos = previousCharPos(S,S.length());
	int tpos = previousCharPos(T,T.length());
	while(spos >= 0 && tpos >= 0) {
		if (S.charAt(spos) != T.charAt(tpos)) {
			return false;
		}
		spos = previousCharPos(S,spos);
		tpos = previousCharPos(T,tpos);
	}
	return spos == tpos;
}