Backspace String Compare (opens in a new tab) Easy

Problem

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Example

Input: S = "ab#c", T = "ad#c"

Output: true

Summary

To solve this problem, we can use two pointers that move through the strings s and t from the end to the beginning, skipping characters that have been deleted by the backspace key (#). When the pointers reach valid characters, we compare them, and if they are different, we return false. If the comparison finishes without finding differences, we return true.

Solution

In TypeScript

function backspaceCompare(s: string, t: string): boolean {
	let p1 = s.length - 1;
	let p2 = t.length - 1;
 
	while (p1 >= 0 || p2 >= 0) {
		let sBackspaces = 0;
		let tBackspaces = 0;
 
		while (p1 >= 0 && (s[p1] === '#' || sBackspaces > 0)) {
			s[p1] === '#' ? sBackspaces++ : sBackspaces--;
			p1--;
		}
 
		while (p2 >= 0 && (t[p2] === '#' || tBackspaces > 0)) {
			t[p2] === '#' ? tBackspaces++ : tBackspaces--;
			p2--;
		}
 
		if (p1 >= 0 && p2 >= 0 && s[p1] !== t[p2]) {
			return false;
		}
 
		if ((p1 >= 0) !== (p2 >= 0)) {
			return false;
		}
 
		p1--;
		p2--;
	}
 
	return true;
}

In Python

def backspaceCompare(self, s: str, t: str) -> bool:
	p1 = len(s) - 1
	p2 = len(t) - 1
 
	while p1 >= 0 or p2 >= 0:
		s_backspaces = 0
		t_backspaces = 0
 
		while p1 >= 0 and (s[p1] == '#' or s_backspaces > 0):
			s_backspaces += 1 if s[p1] == '#' else -1
			p1 -= 1
 
		while p2 >= 0 and (t[p2] == '#' or t_backspaces > 0):
			t_backspaces += 1 if t[p2] == '#' else -1
			p2 -= 1
 
		if p1 >= 0 and p2 >= 0 and s[p1] != t[p2]:
			return False
 
		if (p1 >= 0) != (p2 >= 0):
			return False
 
		p1 -= 1
		p2 -= 1
 
	return True

Step-by-step explanation

1. We initialize two pointers, p1 and p2, to point at the last characters of strings s and t respectively.

let p1 = s.length - 1;
let p2 = s.length - 1;

2. We start a while loop that continues as long as either p1 or p2 is greater than or equal to 0. This means we will keep iterating until both pointers have traversed the entire strings s and t.

while (p1 >= 0 || p2 >= 0) {
	// ...
}

3. Within the while loop, we initialize two counters, sBackspaces and tBackspaces, to count the number of backspaces (#) encountered in s and t respectively.

let sBackspaces = 0;
let tBackspaces = 0;

4. We use two nested while loops to move the pointers p1 and p2 backwards through s and t to skip characters that have been "deleted" by the backspace key (#). We increment the corresponding backspace counters when encountering a # character and decrement them when we find a regular character that is "deleted" by a backspace.

while (p1 >= 0 && (S[p1] === '#' || sBackspaces > 0)) {
	s[p1] === '#' ? sBackspaces++ : sBackspaces--;
	p1--;
}
 
while (p2 >= 0 && (T[p2] === '#' || tBackspaces > 0)) {
	t[p2] === '#' ? tBackspaces++ : tBackspaces--;
	p2--;
}

5. After both nested while loops, the pointers p1 and p2 should point at valid (undeleted) characters or be less than 0 (indicating the beginning of the string has been reached). We then compare the characters at p1 and p2. If they are different, we return false, as the two strings are not equal.

if (p1 >= 0 && p2 >= 0 && S[p1] !== T[p2]) {
	return false;
}

6. If only one of the pointers is greater than or equal to 0, it means one string has been fully traversed, while the other still has valid characters. In this case, we return false, as the strings are not equal.

if ((p1 >= 0) !== (p2 >= 0)) {
	return false;
}

7. If none of the above conditions are met, we move both pointers one step backwards and continue with the next iteration of the while loop.

p1--;
p2--;

8. If the while loop completes without returning false, it means both strings are equal after processing the backspaces. Therefore, we return true.

return true;

By following these steps, the function backspaceCompare determines whether the two strings S and T are equal after simulating typing them into empty text editors, considering the backspace key (#).

Complexity Analysis

Time Complexity

The time complexity of this solution is O(m + n), where m is the length of string S and n is the length of string T. In the worst case, we need to traverse both strings from end to beginning once.

Space Complexity

The space complexity of this solution is O(1), as we only use constant extra space for the pointers and counters.