844. Backspace String Compare
Problem Description
This problem involves comparing two strings to determine if they are the same after processing all backspace operations. In the strings, each #
character represents a backspace operation. The backspace operation removes the character immediately before it, or does nothing if there is no character to remove (i.e., at the beginning of the string). The goal is to return true
if, after applying all backspace operations, the two strings are equal, otherwise return false
.
Let's consider an example. If we have the string "ab#c"
, processing the backspace operations would result in the string "ac"
, since the #
removes the preceding b
. On the other hand, "a#d#"
after processing would become ""
, as both characters are removed by backspaces.
The challenge is to do this comparison efficiently without actually reconstructing the strings after applying the backspace operations.
Intuition
The solution is based on traversing both strings from the end to the start, simulating the backspace operations as we go. This way, we can compare characters that would appear on screen without building the resultant strings.
Here's how we can think about the problem:
- We start by pointing at the last characters of both
s
andt
. - We move backwards through each string. Whenever we encounter a
#
, it signifies that we need to skip the next non-#
character since it is "backspaced." We keep a count of how many characters to skip. - Whenever we are not supposed to skip characters (the skip count is zero), we compare the characters at the current position in both
s
andt
. If they are different, we returnfalse
. - If we reach the beginning of one string but not the other (meaning one string has more characters that would appear on screen than the other), the strings are not equal, and we return
false
. - If both pointers reach the beginning without finding any mismatch, the strings are the same after processing backspaces, and we return
true
.
In summary, the intuition is to iterate from the end to the beginning of the strings while keeping track of backspaces, hence ensuring that only characters that would appear on the screen are compared.
Learn more about Stack and Two Pointers patterns.
Solution Approach
The implementation uses a two-pointer approach. This means we have a pointer for each string (s
and t
), starting from the end of the strings and moving towards the beginning. The variables i
and j
serve as pointers for strings s
and t
, respectively.
Here's a step-by-step explanation of the solution:
- Initialize pointers
i
andj
to the last indices ofs
andt
respectively. - Use two additional variables
skip1
andskip2
to keep track of the number of backspaces (#
) encountered in each string. These variables indicate how many characters we should skip over as we move backwards. - Use a
while
loop to walk through both strings concurrently until both pointers reach the beginning of their respective strings.- For each string
s
andt
, if the current character is#
, increment the respective skip variable (skip1
fors
andskip2
fort
) and move the pointer one step back. - If the current character is not
#
and the skip variable is greater than zero, decrement the skip variable and move the pointer one step back without comparing any characters. This simulates the backspace operation. - If the current character is not
#
and the skip variable is zero, this is a character that would actually appear on screen, and we can pause this step to compare it against the character in the other string.
- For each string
- Compare the characters from each string that are at the current positions:
- If both pointers are within the bounds of their strings and the characters are different, return
false
. - If one pointer is within the bounds of its string and the other is not, return
false
, because one string has more visible characters than the other.
- If both pointers are within the bounds of their strings and the characters are different, return
- Decrement both pointers
i
andj
and return to step 3, continuing this process. - Once both strings have been fully processed, if no mismatches were found, the function returns
true
.
The beauty of this algorithm is that it simulates the text editing process without needing extra space to store the resultant strings after backspace operations, making it an efficient solution in terms of space complexity, which is O(1). The time complexity of the algorithm is O(N + M), where N and M are the lengths of strings s
and t
respectively, as each character in both strings is visited at most twice.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use the solution approach to compare two example strings, s = "ab##"
and t = "c#d#"
to determine if they are equal after processing backspace operations.
We'll walk through each step of the solution:
- Initialize pointers
i
to index 3 (last index ofs
) andj
to index 3 (last index oft
). - Initialize skip variables
skip1
andskip2
to 0.
Step-by-step processing:
-
Iteration 1:
s[i]
is#
so we incrementskip1
to 1 and decrementi
to 2.t[j]
is#
so we incrementskip2
to 1 and decrementj
to 2.
-
Iteration 2:
s[i]
is#
again, so nowskip1
becomes 2 andi
is decremented to 1.t[j]
isd
, butskip2
is 1, so we decrementskip2
to 0 andj
to 1 without comparing the characters.
-
Iteration 3:
s[i]
isb
, butskip1
is 2, so we decrementskip1
to 1 andi
to 0.t[j]
isc
, andskip2
is 0, so we should comparet[j]
withs[i]
. However, we noticeskip1
is still greater than 0, so we decrementskip1
to 0 andi
is now -1 (out of bounds).
-
Iteration 4:
i
is out of bounds, so we can't processs
anymore.t[j]
isc
andskip2
is 0, soc
would be a character that should appear on the screen. Sincei
is out of bounds, we compare an out-of-boundss[i]
witht[j]
which has a visible character 'c'.
-
Conclusion:
- Since
i
is out of bounds andj
points to a visible character, the strings are not the same after processing the backspace operations. We don't need to check the remaining characters ins
since we know at this point that the visible characters are different.
- Since
Hence, the function would return false
. This example demonstrates that string s
becomes empty after applying all backspace operations whereas string t
results in the character 'c', making the strings unequal.
Solution Implementation
1class Solution:
2 def backspace_compare(self, string1: str, string2: str) -> bool:
3 # Initialize pointers for both strings starting from the end
4 index1, index2 = len(string1) - 1, len(string2) - 1
5 # Initialize counters for skip characters ('#')
6 skip_count1, skip_count2 = 0, 0
7
8 # Compare characters in the strings from the end
9 while index1 >= 0 or index2 >= 0:
10 # Find the position of next valid character in string1
11 while index1 >= 0:
12 if string1[index1] == '#':
13 skip_count1 += 1
14 index1 -= 1
15 elif skip_count1 > 0:
16 skip_count1 -= 1
17 index1 -= 1
18 else:
19 break # Found a valid character
20
21 # Find the position of next valid character in string2
22 while index2 >= 0:
23 if string2[index2] == '#':
24 skip_count2 += 1
25 index2 -= 1
26 elif skip_count2 > 0:
27 skip_count2 -= 1
28 index2 -= 1
29 else:
30 break # Found a valid character
31
32 # If both strings have valid characters to compare
33 if index1 >= 0 and index2 >= 0:
34 if string1[index1] != string2[index2]:
35 # Characters do not match
36 return False
37 # If one index is negative, it means one string has more characters left after processing backspaces
38 elif index1 >= 0 or index2 >= 0:
39 return False
40
41 # Move to the next character
42 index1, index2 = index1 - 1, index2 - 1
43
44 # If all characters matched, return True
45 return True
46
1class Solution {
2 public boolean backspaceCompare(String s, String t) {
3 // Initialize two pointers for iterating through the strings in reverse.
4 int pointerS = s.length() - 1, pointerT = t.length() - 1;
5 // Variables to keep track of the number of backspaces found.
6 int skipS = 0, skipT = 0;
7
8 // Continue comparing characters until both pointers go beyond the start of the string.
9 while (pointerS >= 0 || pointerT >= 0) {
10 // Process backspaces in string s.
11 while (pointerS >= 0) {
12 if (s.charAt(pointerS) == '#') {
13 skipS++; // We found a backspace character.
14 pointerS--; // Move one character back.
15 } else if (skipS > 0) {
16 skipS--; // Reduce the backspace count.
17 pointerS--; // Skip over this character.
18 } else {
19 break; // Found a character to compare.
20 }
21 }
22 // Process backspaces in string t.
23 while (pointerT >= 0) {
24 if (t.charAt(pointerT) == '#') {
25 skipT++; // We found a backspace character.
26 pointerT--; // Move one character back.
27 } else if (skipT > 0) {
28 skipT--; // Reduce the backspace count.
29 pointerT--; // Skip over this character.
30 } else {
31 break; // Found a character to compare.
32 }
33 }
34
35 // Compare the characters of both strings.
36 if (pointerS >= 0 && pointerT >= 0) {
37 // If characters do not match, return false.
38 if (s.charAt(pointerS) != t.charAt(pointerT)) {
39 return false;
40 }
41 } else if (pointerS >= 0 || pointerT >= 0) {
42 // If one pointer has reached the start but the other has not, they do not match.
43 return false;
44 }
45 // Move to the next characters to compare.
46 pointerS--;
47 pointerT--;
48 }
49 // All characters match considering the backspace characters.
50 return true;
51 }
52}
53
1class Solution {
2public:
3 // Function to compare two strings considering '#' as a backspace character.
4 bool backspaceCompare(string s, string t) {
5 // Initialize two pointers for the end of the strings.
6 int sIndex = s.size() - 1, tIndex = t.size() - 1;
7 // Initialize counters for the number of backspaces in s and t.
8 int sSkip = 0, tSkip = 0;
9
10 // While there are characters to compare in either string.
11 while (sIndex >= 0 || tIndex >= 0) {
12 // Find position of next possible character in s.
13 while (sIndex >= 0) {
14 if (s[sIndex] == '#') { // If a backspace char found, increment the skip counter.
15 ++sSkip;
16 --sIndex;
17 } else if (sSkip > 0) { // If we have backspaces to apply, decrement the counter and index.
18 --sSkip;
19 --sIndex;
20 } else {
21 break; // Found a valid character to compare.
22 }
23 }
24
25 // Find position of next possible character in t.
26 while (tIndex >= 0) {
27 if (t[tIndex] == '#') { // If a backspace char found, increment the skip counter.
28 ++tSkip;
29 --tIndex;
30 } else if (tSkip > 0) { // If we have backspaces to apply, decrement the counter and index.
31 --tSkip;
32 --tIndex;
33 } else {
34 break; // Found a valid character to compare.
35 }
36 }
37
38 // If both current indices are valid, compare the characters from s and t.
39 if (sIndex >= 0 && tIndex >= 0) {
40 // If the characters are different, return false.
41 if (s[sIndex] != t[tIndex]) return false;
42 } else if (sIndex >= 0 || tIndex >= 0) {
43 // If one string has ended, but the other has not, they are not the same.
44 return false;
45 }
46
47 // Move to the next character in each string.
48 --sIndex;
49 --tIndex;
50 }
51
52 // All compared characters are equal, return true.
53 return true;
54 }
55};
56
1function backspaceCompare(S: string, T: string): boolean {
2 // Initialize two pointers, starting from the end of each string.
3 let pointerS = S.length - 1;
4 let pointerT = T.length - 1;
5
6 // Continue comparing as long as there's a character in either string.
7 while (pointerS >= 0 || pointerT >= 0) {
8 let skipS = 0; // To count the backspaces in S.
9 // Processing backspaces for S.
10 while (pointerS >= 0) {
11 if (S[pointerS] === '#') {
12 skipS++; // Found a backspace; increase count.
13 } else if (skipS > 0) {
14 skipS--; // Skip the character due to a previous backspace.
15 } else {
16 break; // Found a valid character to compare.
17 }
18 pointerS--; // Move backwards in string S.
19 }
20
21 let skipT = 0; // To count the backspaces in T.
22 // Processing backspaces for T.
23 while (pointerT >= 0) {
24 if (T[pointerT] === '#') {
25 skipT++; // Found a backspace; increase count.
26 } else if (skipT > 0) {
27 skipT--; // Skip the character due to a previous backspace.
28 } else {
29 break; // Found a valid character to compare.
30 }
31 pointerT--; // Move backwards in string T.
32 }
33
34 // Compare the characters of S and T at the pointers.
35 if (pointerS >= 0 && pointerT >= 0 && S[pointerS] !== T[pointerT]) {
36 return false; // Characters do not match.
37 }
38
39 // If one string is at the end, make sure the other is too.
40 if ((pointerS >= 0) !== (pointerT >= 0)) {
41 return false; // One string ended prematurely.
42 }
43
44 // Move to the next valid character in the string.
45 pointerS--;
46 pointerT--;
47 }
48
49 // All compared characters matched.
50 return true;
51}
52
Time and Space Complexity
The time complexity of the given code is O(N + M), where N
is the length of string s
and M
is the length of string t
. This is because in the worst case, the algorithm may have to iterate through all the characters in both strings once. The backspace character (#
) processing only increases the number of iterations by a constant factor, not the overall complexity.
The space complexity of the code is O(1). This is because the space required for the variables i
, j
, skip1
, and skip2
does not depend on the size of the input strings, making it constant space.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Don’t Miss This!