I like to read this solution as a small machine: keep the useful information, throw away the noise. For 282. Expression Add Operators, the solution in this repository is mainly a backtracking solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. 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: backtracking.
The notes already sitting in the source point us in the right direction:
- backtracking
- TLE
- 3 / 20 test cases passed.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are stringIsNumber, evaluate, backtrack, addOperators, expr.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- Substring checks are convenient but not free, so they are part of the real complexity story.
- 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:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
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//backtracking
02//TLE
03//3 / 20 test cases passed.
04class Solution {
05public:
06 vector<char> operators;
07
08 bool stringIsNumber(string& s){
09 return !s.empty() && s.find_first_not_of("0123456789") == std::string::npos;
10 }
11
12 long long evaluate(string& expr){
13 // cout << "expr: " << expr << endl;
14 deque<string> deq;
15 //'*' has highest priority, process it immediately after we meet it
16 for(int i = 0; i < expr.size(); i++){
17 char c = expr[i];
18 if(c == '*'){
19 long long operand1 = stoll(deq.back()); deq.pop_back();
20 long long operand2 = expr[++i] - '0';
21 // cout << "meet * " << operand1 << " and " << operand2 << endl;
22 //calculate immediately and push to deq
23 deq.push_back(to_string(operand1 * operand2));
24 }else if(!deq.empty() && stringIsNumber(deq.back()) && isdigit(c)){
25 //extend previous number
26 deq.back() += c;
27 }else{
28 deq.push_back(string(1, c));
29 }
30 // cout << "deq: ";
31 // for(string s : deq){
32 // cout << s << " ";
33 // }
34 // cout << endl;
35 }
36
37 //no '+' or '-' in expr
38 if(deq.size() == 1){
39 long long res = stoll(deq.back());
40 // cout << "res: " << res << endl;
41 return res;
42 }
43
44 //now there are only '+' and '-'
45
46 /*
47 important!
48 now access the deque from front!
49 because when there are + and -,
50 expressions should be evaluated in FIFO order
51 */
52 long long res = stoll(deq.front()); deq.pop_front();
53 while(!deq.empty() && stringIsNumber(deq.front())){
54 res = res * 10 + stoll(deq.front()); deq.pop_front();
55 }
56
57 while(!deq.empty()){
58 //pop one operator and one operand at a time
59 char c = deq.front()[0]; deq.pop_front();
60 long long operand2 = stoll(deq.front()); deq.pop_front();
61
62 if(c == '+'){
63 res = res + operand2;
64 }else if(c == '-'){
65 res = res - operand2;
66 }
67 }
68
69 // cout << "res: " << res << endl;
70
71 return res;
72 }
73
74 void backtrack(vector<string>& exprs, string& expr, string& num, int target, int start){
75 if(start == num.size()){
76 if(evaluate(expr) == target){
77 exprs.push_back(expr);
78 }
79 }else{
80 for(char op : operators){
81 if(!expr.empty() && expr.back() == '0' && op == '\0'){
82 //avoid generating "1+05"
83 continue;
84 }
85 if(op != '\0') expr += op;
86 expr += num[start];
87 backtrack(exprs, expr, num, target, start+1);
88 // cout << "before erase: " << expr << endl;
89 //erase two chars if we have added op
90 expr.erase(expr.size()-(1 + (op != '\0')), 1 + (op != '\0'));
91 // cout << "after erase: " << expr << endl;
92 }
93 }
94 }
95
96 vector<string> addOperators(string num, int target) {
97 //'\0' means add nothing
98 operators = {'\0', '+', '-', '*'};
99 vector<string> exprs;
100 if(num.size() == 0) return {""};
101 string expr(1, num[0]);
102
103 backtrack(exprs, expr, num, target, 1);
104
105 return exprs;
106 }
107};
108
109//backtrack, evaluate expression on the fly
110//WA
111//14 / 20 test cases passed.
112class Solution {
113public:
114 vector<char> operators;
115
116 void backtrack(vector<string>& exprs, string& expr, string& num, int target, int start, long long res, int lastOperand, char lastOperator){
117 // cout << "expr: " << expr << ", start: " << start << ", res: " << res << ", lastOperand: " << lastOperand << ", lastOp: " << lastOperator << endl;
118 //res: current evaluated result of expr
119 if(start == num.size()){
120 // cout << "expr: " << expr << endl;
121 //expr is already evaluated on the fly!
122 if(res == target){
123 exprs.push_back(expr);
124 }
125 // }else if(log10(res) - (num.size() - start) > log10(target)+1){
126 // //early stopping
127 // cout << res << ", " << start << ", " << target << endl;
128 }else{
129 int digit = num[start] - '0';
130 for(char op : operators){
131 int lastRes = res;
132 // cout << "curOp: " << op << ", res: " << res << ", lastOp: " << lastOperator << ", lastOperand: " << lastOperand << endl;
133 if(!expr.empty() && expr.back() == '0' && op == '\0'){
134 //avoid generating "1+05"
135 continue;
136 }
137 if(op != '\0') expr += op;
138 expr += num[start];
139 //calculate res on the fly!
140 switch(op){
141 case '+':
142 res += digit;
143 // lastOperator = '+';
144 break;
145 case '-':
146 res -= digit;
147 // lastOperator = '-';
148 break;
149 case '*':
150 //special case, '*' has higher precedence!
151 switch(lastOperator){
152 case '+':
153 //undo previous operation
154 res -= lastOperand;
155 //'*' has higher precedence than '+'
156 res = res + lastOperand * digit;
157 break;
158 case '-':
159 //undo previous operation
160 res += lastOperand;
161 //'*' has higher precedence than '-'
162 res = res - lastOperand * digit;
163 break;
164 case '*':
165 //what if "10+2*3*4"?
166 case '\0':
167 //directly multiply?
168 res *= digit;
169 }
170 /*
171 don't change lastOperator, only change lastOperand
172 since there is no chance that we undo the '*' operation!
173 */
174 // lastOperand *= digit;
175 // curOperand = lastOperand * digit;
176 //lastOperator = '*';
177 break;
178 case '\0':
179 //special case, '*' has higher precedence!
180 switch(lastOperator){
181 case '+':
182 //undo previous operation
183 res -= lastOperand;
184 //'\0' has higher precedence than '+'
185 res = res + (lastOperand * 10 + digit);
186 break;
187 case '-':
188 //undo previous operation
189 res += lastOperand;
190 //'\0' has higher precedence than '-'
191 res = res - (lastOperand * 10 + digit);
192 break;
193 case '*':
194 case '\0':
195 //directly update?
196 res = (res * 10 + digit);
197 }
198 // lastOperator = '\0';
199 break;
200 }
201 // lastOperand = digit;
202 backtrack(exprs, expr, num, target, start+1, res,
203 (lastOperator == '*' && op == '*') ? lastOperand * digit: digit,
204 ((op == '*') ? lastOperator: op));
205 // cout << "before erase: " << expr << endl;
206 //erase two chars if we have added op
207 expr.erase(expr.size()-(1 + (op != '\0')), 1 + (op != '\0'));
208 res = lastRes;
209 // cout << "after erase: " << expr << endl;
210 }
211 }
212 }
213
214 vector<string> addOperators(string num, int target) {
215 //'\0' means add nothing
216 operators = {'\0', '+', '-', '*'};
217 vector<string> exprs;
218 if(num.size() == 0) return {""};
219 string expr(1, num[0]);
220 int digit = num[0] - '0';
221
222 backtrack(exprs, expr, num, target, 1, digit, digit, '\0');
223
224 return exprs;
225 }
226};
227
228//backtrack, evaluate expression on the fly, official solution
229//Runtime: 284 ms, faster than 78.51% of C++ online submissions for Expression Add Operators.
230//Memory Usage: 14.4 MB, less than 92.93% of C++ online submissions for Expression Add Operators.
231//time: O(4^N*N), space: O(N)
232class Solution {
233public:
234 vector<char> operators;
235
236 void backtrack(vector<string>& exprs, string& expr, string& num, int target, int start, long long res, long long lastOperand, long long curOperand){
237 // cout << "expr: " << expr << ", start: " << start << ", res: " << res << ", lastOperand: " << lastOperand << ", curOperand: " << curOperand << endl;
238 //res: current evaluated result of expr
239 if(start == num.size()){
240 // cout << "expr: " << expr << endl;
241 // curOperand == 0: no operand is left unprocessed
242 // if(curOperand != 0){
243 // cout << expr << endl;
244 // }
245 if(res == target && curOperand == 0){
246 //there is a '+' beforehand
247 exprs.push_back(expr.substr(1));
248 }
249 }else{
250 int digit = num[start] - '0';
251 curOperand = curOperand * 10 + digit;
252 string strCurOperand = to_string(curOperand);
253 for(char op : operators){
254 //calculate res on the fly!
255 // cout << "digit: " << digit << ", curOperand: " << curOperand << ", op: " << op << endl;
256 switch(op){
257 case '+':
258 expr += op;
259 expr += strCurOperand;
260 //when operator is '+' or '-', we don't need to maintain lastOperand, so we set it to 0
261 /*
262 note that we pass curOperand as the argument lastOperand
263 and 0 as curOperand?
264 */
265 backtrack(exprs, expr, num, target, start+1, res + curOperand, curOperand, 0);
266 /*
267 erase total 1+strCurOperand.size() chars!
268 strCurOperand's length is not always 1!
269 */
270 expr.erase(expr.size()-(1+strCurOperand.size()), 1+strCurOperand.size());
271 break;
272 case '-':
273 if(expr.size() > 0){
274 //don't allow expr starts with '-'
275 expr += op;
276 expr += strCurOperand;
277 /*
278 note that we pass -curOperand as the argument lastOperand
279 and 0 as curOperand?
280 */
281 backtrack(exprs, expr, num, target, start+1, res - curOperand, -curOperand, 0);
282 expr.erase(expr.size()-(1+strCurOperand.size()), 1+strCurOperand.size());
283 }
284 break;
285 case '*':
286 if(expr.size() > 0){
287 //don't allow expr starts with '-'
288 expr += op;
289 expr += strCurOperand;
290 backtrack(exprs, expr, num, target, start+1, res - lastOperand + lastOperand * curOperand, lastOperand * curOperand, 0);
291 expr.erase(expr.size()-(1+strCurOperand.size()), 1+strCurOperand.size());
292 }
293 break;
294 case '\0':
295 if(curOperand > 0){
296 /*
297 note that unlike other operators,
298 we don't append strCurOperand to expr!
299 and also res, lastOperand, curOperand remain the same,
300 that means when meeting '\0',
301 we are still constructing curOperand
302 */
303 //so that we won't build expr like "05"
304 backtrack(exprs, expr, num, target, start+1, res, lastOperand, curOperand);
305 }
306 break;
307 }
308 }
309 }
310 }
311
312 vector<string> addOperators(string num, int target) {
313 if(num.size() == 0) return {};
314 operators = {'\0', '+', '-', '*'};
315 vector<string> exprs;
316 string expr = "";
317
318 backtrack(exprs, expr, num, target, 0, 0, 0, 0);
319
320 return exprs;
321 }
322};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.