Description:
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". Solution:
Time complexity : O(n)
// In this solution we use an array like a stack // to create 2 new strings from the inputs // Then we check if they are equal const backspaceCompare = (S, T) => buildString(S) === buildString(T); // Helper function function buildString(S) { // Data structure that we will use to create the compare strings const stack = []; for (const c of S) { // Add letter to the stack if it is not '#' if (c != '#') stack.push(c); // Remove the most recently added letter if we encounter '#' // and the stack is not empty else if (stack.length!==0) { stack.pop(); } } // Convert array to an string return stack.join(''); } 
Top comments (0)