Backspace String Compare
EasyPrompt
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 <= 200sandtonly contain lowercase letters and'#'characters.
Follow up: Can you solve it in O(n) time and O(1) space?
Approaches
2 approaches with complexity analysis and trade-offs.
This approach simulates the process of typing the characters of each string into a text editor. We can build the final resulting strings for both s and t after processing all the backspace characters. Finally, we compare the two built strings to see if they are identical.
Algorithm
- Create a helper function
build(String str). - Inside
build, initialize an emptyStringBuilder. - Iterate through each character of the input string
str. - If the character is not '#', append it to the
StringBuilder. - If the character is '#' and the
StringBuilderis not empty, remove its last character. - After the loop, return the string representation of the
StringBuilder. - In the main function, call
build(s)andbuild(t). - Compare the two resulting strings for equality and return the result.
Walkthrough
We can write a helper function that takes a string and returns its final version after applying backspaces. This function iterates through the input string and uses a StringBuilder (or a stack) to construct the result.
- When a non-backspace character is encountered, it's appended to the
StringBuilder. - When a backspace character ('#') is found, if the
StringBuilderis not empty, the last character is deleted. - After processing both
sandtwith this helper function, we get two final strings. The problem then reduces to a simple string comparison.
class Solution { public boolean backspaceCompare(String s, String t) { return build(s).equals(build(t)); } private String build(String str) { StringBuilder sb = new StringBuilder(); for (char c : str.toCharArray()) { if (c != '#') { sb.append(c); } else if (sb.length() > 0) { sb.deleteCharAt(sb.length() - 1); } } return sb.toString(); }}Complexity
Time
O(N + M), where N and M are the lengths of strings `s` and `t` respectively. We iterate through each string once to build the final strings, and then compare them.
Space
O(N + M). In the worst case (no backspaces), the `StringBuilder`s will store all characters of the original strings, where N and M are the lengths of s and t.
Trade-offs
Pros
Conceptually simple and easy to implement.
The logic directly follows the problem description.
Cons
Requires extra space proportional to the input string lengths, which does not meet the follow-up constraint of O(1) space.
Solutions
Solution
class Solution {public boolean backspaceCompare(String s, String t) { int i = s.length() - 1, j = t.length() - 1; int skip1 = 0, skip2 = 0; for (; i >= 0 || j >= 0; --i, --j) { while (i >= 0) { if (s.charAt(i) == '#') { ++skip1; --i; } else if (skip1 > 0) { --skip1; --i; } else { break; } } while (j >= 0) { if (t.charAt(j) == '#') { ++skip2; --j; } else if (skip2 > 0) { --skip2; --j; } else { break; } } if (i >= 0 && j >= 0) { if (s.charAt(i) != t.charAt(j)) { return false; } } else if (i >= 0 || j >= 0) { return false; } } return true; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.