This problem looks busy at first, but the accepted solution is built around one steady invariant. For 844. Backspace String Compare, the solution in this repository is mainly a stack solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: stack.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are backspaceCompare.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- The stack stores unfinished context, which is usually the cleanest way to handle nested or monotonic structure.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.
03
04Example 1:
05
06Input: S = "ab#c", T = "ad#c"
07Output: true
08Explanation: Both S and T become "ac".
09Example 2:
10
11Input: S = "ab##", T = "c#d#"
12Output: true
13Explanation: Both S and T become "".
14Example 3:
15
16Input: S = "a##c", T = "#a#c"
17Output: true
18Explanation: Both S and T become "c".
19Example 4:
20
21Input: S = "a#c", T = "b"
22Output: false
23Explanation: S becomes "c" while T becomes "b".
24Note:
25
261 <= S.length <= 200
271 <= T.length <= 200
28S and T only contain lowercase letters and '#' characters.
29Follow up:
30
31Can you solve it in O(N) time and O(1) space?
32**/
33
34//Runtime: 4 ms, faster than 100.00% of C++ online submissions for Backspace String Compare.
35//Memory Usage: 8.6 MB, less than 98.93% of C++ online submissions for Backspace String Compare.
36
37class Solution {
38public:
39 bool backspaceCompare(string S, string T) {
40 stack<char> stkS, stkT;
41
42 for(char c : S){
43 if(c == '#' && !stkS.empty()) stkS.pop();
44 else if(c != '#') stkS.push(c);
45 //ignore '#' when stack is empty
46 }
47
48 for(char c : T){
49 if(c == '#' && !stkT.empty()) stkT.pop();
50 else if(c != '#') stkT.push(c);
51 }
52
53 if(stkS.size() != stkT.size()) return false;
54
55 while(!stkS.empty() && !stkT.empty()){
56 char cS = stkS.top(), cT = stkT.top();
57 if(cS != cT) return false;
58 stkS.pop();
59 stkT.pop();
60 }
61
62 if(!stkS.empty() || !stkT.empty()) return false;
63 return true;
64 }
65};
66
67/**
68Approach #1: Build String [Accepted]
69**/
70/**
71Complexity Analysis
72
73Time Complexity: O(M + N)O(M+N), where M, NM,N are the lengths of S and T respectively.
74
75Space Complexity: O(M + N)O(M+N).
76**/
77
78/**
79Approach #2: Two Pointer [Accepted]
80Intuition
81
82When writing a character, it may or may not be part of the final string depending on how many backspace keystrokes occur in the future.
83
84If instead we iterate through the string in reverse, then we will know how many backspace characters we have seen, and therefore whether the result includes our character.
85
86Algorithm
87
88Iterate through the string in reverse. If we see a backspace character, the next non-backspace character is skipped. If a character isn't skipped, it is part of the final answer.
89
90See the comments in the code for more details.
91**/
92/*8
93Complexity Analysis
94
95Time Complexity: O(M + N)O(M+N), where M, NM,N are the lengths of S and T respectively.
96
97Space Complexity: O(1)O(1).**/
98
99//Runtime: 4 ms, faster than 100.00% of C++ online submissions for Backspace String Compare.
100//Memory Usage: 8.3 MB, less than 100.00% of C++ online submissions for Backspace String Compare.
101/**
102class Solution {
103public:
104 bool backspaceCompare(string S, string T) {
105 int curS = S.size()-1, curT = T.size()-1;
106 int skipS = 0, skipT = 0;
107
108 //if two string ends concurrently, we return true
109 while(curS >= 0 || curT >= 0){
110 while(curS >= 0){
111 if(S[curS] == '#'){skipS++; curS--;}
112 else if(skipS > 0) {skipS--; curS--;}
113 //find the char not skipped
114 else break;
115 }
116 while(curT >= 0){
117 if(T[curT] == '#'){skipT++; curT--;}
118 else if(skipT > 0) {skipT--; curT--;}
119 else break;
120 }
121 if(curS >= 0 && curT >= 0 && S[curS] != T[curT]) return false;
122 //one string ends earlier than the other
123 if((curS >= 0) != (curT >= 0)) return false;
124 curS--; curT--;
125 }
126 return true;
127 }
128};
129**/Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.