Sponsored
Sponsored
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.
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.
1#include <stdio.h>
2#include <string.h>
3#define MAX_LEN 201
4
5// Helper function to process the string accounting for backspaces
6void buildFinalString(const char* str, char* result) {
7 int j = 0;
8 for (int i = 0; str[i]; i++) {
9 if (str[i] != '#') {
10 result[j++] = str[i];
11 } else if (j > 0) {
12 j--;
13 }
14 }
15 result[j] = '\0';
16}
17
18int backspaceCompare(char * s, char * t) {
19 char finalS[MAX_LEN], finalT[MAX_LEN];
20 buildFinalString(s, finalS);
21 buildFinalString(t, finalT);
22 return strcmp(finalS, finalT) == 0;
23}
24
25int main() {
26 printf("%d\n", backspaceCompare("ab#c", "ad#c")); // 1 (true)
27 printf("%d\n", backspaceCompare("ab##", "c#d#")); // 1 (true)
28 printf("%d\n", backspaceCompare("a#c", "b")); // 0 (false)
29 return 0;
30}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.
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.
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.
1#include <iostream>
#include <string>
using namespace std;
bool backspaceCompare(string s, string t) {
int si = s.length() - 1, ti = t.length() - 1;
int skipS = 0, skipT = 0;
while (si >= 0 || ti >= 0) {
while (si >= 0) {
if (s[si] == '#') { skipS++; si--; }
else if (skipS > 0) { skipS--; si--; }
else break;
}
while (ti >= 0) {
if (t[ti] == '#') { skipT++; ti--; }
else if (skipT > 0) { skipT--; ti--; }
else break;
}
if ((si >= 0 && ti >= 0 && s[si] != t[ti]) || ((si >= 0) != (ti >= 0))) {
return false;
}
si--; ti--;
}
return true;
}
int main() {
cout << backspaceCompare("ab#c", "ad#c") << endl; // true
cout << backspaceCompare("ab##", "c#d#") << endl; // true
cout << backspaceCompare("a#c", "b") << endl; // false
return 0;
}The C++ implementation employs two pointers to iteratively move backwards through the strings, adjusting their position and incrementing or decrementing the backspace counter as needed to simulate the typing effect. We directly compare the characters the pointers land on after properly ignoring the backspaced characters.