844. Backspace String Compare

Amazon

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.

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 = "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?

Solution:

Version 1: 借助栈来存储非‘#’的字符，当非‘#’时，入栈，当得到‘#’时判断是否需要出栈

class Solution {
    public boolean backspaceCompare(String s, String t) {
        return backspacing(s).equals(backspacing(t));
    }
    
    public String backspacing(String word)
    {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i< word.length(); i++)
        {
            if(word.charAt(i) != '#')
            {
                stack.push(word.charAt(i) );
            }else
            {
                if(!stack.isEmpty())
                {
                    stack.pop();
                }
            }
        }
        // 注意这里可以直接将stack转化成String
        return String.valueOf(stack);
    }
}

Version 2: O(1) space

public class Solution {
    public bool BackspaceCompare(string s, string t) {
        int sback=0,tback=0;
        int i=s.Length-1,j=t.Length-1;
        char hash='#';
        
        while(i>=0 || j>=0)
        {
            //find first non # character in s string
            while(i>=0)
            {
                if(s[i]==hash)
                {
                    sback++;
                    i--;
                }
                else if(sback>0)
                {
                    sback--;
                    i--;
                }
                else
                    break;
            }
            
            //find first non # character in t string
            while(j>=0)
            {
                if(t[j]==hash)
                {
                    tback++;
                    j--;
                }
                else if (tback>0)
                {
                    tback--;
                    j--;
                }
                else
                    break;
            }
            
            if(i>=0 && j>=0 && s[i]!=t[j])
                return false;
            if((i>=0) != (j>=0))
                return false;
            
            i--;
            j--;
        }
        
        return true;
    }
}