Problem

Given two strings S and T, return 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.

Note:

1 <= S.length <= 2001 <= T.length <= 200S and T only contain lowercase letters and ‘#’ characters.

Follow up:

Can you solve it in O(N) time and O(1) space?

Example1

Input: S = “ab#c”, T = “ad#c” Output: true Explanation: Both S and T become “ac”.

Example2

Input: S = “ab##”, T = “c#d#” Output: true Explanation: Both S and T become “”.

Example3

Input: S = “a##c”, T = “#a#c” Output: true Explanation: Both S and T become “c”.

Example4

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

Solution

class Solution { public: bool backspaceCompare(string S, string T) { stack<char> S_stk; stack<char> T_stk; for(auto c:S) { if(c != '#') S_stk.push(c); else { if(S_stk.empty()) continue; else S_stk.pop(); } } for(auto c:T) { if(c != '#') T_stk.push(c); else { if(T_stk.empty()) continue; else T_stk.pop(); } } if(S_stk.size() != T_stk.size()) return false; while(!S_stk.empty()) { if(S_stk.top() != T_stk.top()) return false; S_stk.pop(); T_stk.pop(); } return true; } };