Day 9 of 30-Day LeetCode Challenge

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.

class Solution {
public:
bool backspaceCompare(string S, string T) {
//Approach 1 : using stacks O(m+n) time & O(m+n) space
// stack<char> st1, st2;

// for(int i=0;i<S.size();++i){
// if(S[i]==’#’&&st1.size()>0) st1.pop();
// else if(S[i]!=’#’) st1.push(S[i]);
// }

// for(int i=0;i<T.size();++i){
// if(T[i]==’#’&&st2.size()>0) st2.pop();
// else if(T[i]!=’#’) st2.push(T[i]);
// }

// if(st1.size()!=st2.size()) return false;

// while(!st1.empty()){
// if(st1.top()!=st2.top()){
// return false;
// }
// st1.pop();
// st2.pop();
// }
// return true;

//Approach 2 : iterate in reverse O(m+n) time & O(1) space
string res1 = “”, res2 = “”;
int backSpaceCount = 0;
for(int i=S.size()-1;i>=0; — i){
if(S[i]==’#’) ++backSpaceCount;
else if(backSpaceCount==0){
res1 += S[i];
}else if(backSpaceCount>0) {
— backSpaceCount;
}
}
backSpaceCount = 0;
for(int i=T.size()-1;i>=0; — i){
if(T[i]==’#’) ++backSpaceCount;
else if(backSpaceCount==0){
res2 += T[i];
}else if(backSpaceCount>0) {
— backSpaceCount;
}
}

return (res1==res2)?true:false;

}
};