Blogs Hub

by Sumit Chourasia | Oct 02, 2020 | Category :coding | Tags : algorithm data-structure easy leetcode

Backspace String Compare - Math - Easy - LeetCode

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.
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)

Contributed By: Sumit Chourasia
Reformat Department Table - Sql - Easy - LeetCode
Contributed By: Sumit Chourasia
Combination Sum II - Array - Medium - LeetCode
Contributed By: Sumit Chourasia
Unique Paths II - Array - Medium - LeetCode