Given two strings s and t, return true 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 = "b" Output: false Explanation: s becomes "c" while t becomes "b".
Constraints:
1 <= s.length, t.length <= 200s and t only contain lowercase letters and '#' characters.
Follow up: Can you solve it in O(n) time and O(1) space?
This approach simulates the typing process using two stacks, one for each string. We iterate over each string, using the stack to build the string as it would appear after considering the backspace characters ('#'). By comparing the final stack representations, we can determine if the two strings are equivalent.
The C solution uses an auxiliary array to simulate a stack where each character is pushed unless it is a '#'. If a '#' is encountered and the stack is not empty, the top character is popped (or removed). After processing both strings, we compare the resulting arrays to determine if they are equivalent.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m), where n and m are the lengths of s and t. Each character is processed once.
Space Complexity: O(n + m) due to the auxiliary arrays used to store the processed results of s and t.
This approach avoids extra space by using two pointers to traverse the strings backwards. By skipping over characters that are effectively backspaced due to a '#' character, we can compare corresponding positions in each string without actually building the resultant strings.
The C implementation of the two-pointer technique uses two pointers to scan the strings from the end to the beginning. We manage two skip counters to skip over unnecessary characters, effectively simulating the result of backspaces without extra space. If the strings differ at any point of effective characters, we return false; otherwise, we return true.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m), where n and m are the lengths of s and t.
Space Complexity: O(1), since we only use constant space.
| Approach | Complexity |
|---|---|
| Using a Stack to Simulate Typing | Time Complexity: O(n + m), where n and m are the lengths of s and t. Each character is processed once. |
| Two-Pointer Technique | Time Complexity: O(n + m), where n and m are the lengths of s and t. |
Backspace String Compare • Kevin Naughton Jr. • 32,882 views views
Watch 9 more video solutions →Practice Backspace String Compare with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor