0844 - Backspace String Compare

0844 - Backspace String Compare

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Examples

Input: s = "ab#c", t = "ad#c" Output: true Explanation: Both s and t become "ac".

Input: s = "ab##", t = "c#d#" Output: true Explanation: Both s and t become "".

Input: s = "a##c", t = "#a#c" Output: true Explanation: Both s and t become "c".

Input: s = "a#c", t = "b" Output: false Explanation: s becomes "c" while t becomes "b".

Constraints

1 <= s.length, t.length <= 200 s and t only contain lowercase letters and '#' characters.

Follow up: Can you solve it in O(n) time and O(1) space?

Java Solution

Stack Based

class Solution {
    public boolean backspaceCompare(String s, String t) {
        return helper(s).equals(helper(t));
    }
    
    private String helper(String str) {
        Stack<Character> stack = new Stack();
        
        for(char c : str.toCharArray()) {
            if(c != '#') stack.push(c);
            else if(!stack.isEmpty()) stack.pop();
        }
        
        return String.valueOf(stack);
    }
}

Two Pointer

class Solution {
    public boolean backspaceCompare(String s, String t) {
        int sl = s.length()-1;
        int tl = t.length()-1;
        
        int sCount = 0;
        int tCount = 0;
        
        while(sl >= 0 || tl >= 0) {
            while(sl >= 0) {
                if(s.charAt(sl) == '#') {
                    sCount++;
                    sl--;
                } else if(sCount > 0) {
                    sl--;
                    sCount--;
                } else break;
            }
            
            while(tl >= 0) {
                if(t.charAt(tl) == '#') {
                    tCount++;
                    tl--;
                } else if(tCount > 0) {
                    tl--;
                    tCount--;
                } else break;
            }
            
            if(sl >= 0 && tl >= 0 && s.charAt(sl) != t.charAt(tl)) return false;
            if ((sl >= 0) != (tl >= 0))
                return false;
            sl--;
            tl--;
        }
        return true;
    }

}