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 <iostream>
2#include <stack>
3#include <string>
4
5using namespace std;
6
7string buildFinalString(const string &str) {
8 stack<char> s;
9 for (char ch : str) {
10 if (ch != '#') {
11 s.push(ch);
12 } else if (!s.empty()) {
13 s.pop();
14 }
15 }
16 string result;
17 while (!s.empty()) {
18 result += s.top();
19 s.pop();
20 }
21 reverse(result.begin(), result.end());
22 return result;
23}
24
25bool backspaceCompare(string s, string t) {
26 return buildFinalString(s) == buildFinalString(t);
27}
28
29int main() {
30 cout << backspaceCompare("ab#c", "ad#c") << endl; // true
31 cout << backspaceCompare("ab##", "c#d#") << endl; // true
32 cout << backspaceCompare("a#c", "b") << endl; // false
33 return 0;
34}This C++ solution uses a stack to simulate building the final string. We iterate through the string and push characters onto the stack unless it's a '#', in which case we pop the top character if the stack is not empty. Finally, we reverse the stack's contents to get the built string and compare the two results for equality.
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
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.