# Blogs Hub

### by Sumit Chourasia | Oct 02, 2020 | Category :coding | Tags : algorithmdata-structureeasyleetcode #### Backspace String Compare - Math - Easy - LeetCode

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.

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".
Note:

1 <= S.length <= 200
1 <= T.length <= 200
S and T only contain lowercase letters and '#' characters.

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

``````public class Solution {
public bool BackspaceCompare(string S, string T) {
var stack1 = new Stack<char>();
var stack2 = new Stack<char>();
for(int i=0;i<S.Length;i++){
if(S[i]=='#'){
if(stack1.Count!=0){
stack1.Pop();
}
}
else{
stack1.Push(S[i]);
}
}

for(int i=0;i<T.Length;i++){
if(T[i]=='#'){
if(stack2.Count!=0){
stack2.Pop();
}
}
else{
stack2.Push(T[i]);
}
}

if(stack1.Count != stack2.Count){
return false;
}

while(stack1.Count>0){
if(stack1.Pop()!=stack2.Pop()){
return false;
}
}

return true;
}
}``````

Time Complexity: O(n)

Space Complexity: O(n)