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. Follow up:
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)
