Leetcode: Day 130, #282 #286 Expression Add Operators, Walls and Gates

Leetcode: Day 130, #282 #286 Expression Add Operators, Walls and Gates

Day 130, #282 #286 Expression Add Operators, Walls and Gates Expression Add Operators 0-9 + ,  -  between the digits so they evaluate to the target value. Examples:  --------------------------------------------------------------------------- 如果遇到"*"，则返回之前的操作（因为之前的运算符和值都已经存好） 1 + 2 * 3,之前 1 + 2已经算出为3，之前的运算符为+，值为2。然后此时 总值- 2 + 2 * 3 cur为当前的总值，op为之前运算符，val为上一步计算的值 class Solution { public: int target; void dfs(vector &rt,string num,int index,string sofar,long cur,string op,long val) { if (index == num.length() && target == cur) { rt.push_back(sofar); } for (int i = index; i < num.length(); i++) { string s = num.substr(index,i + 1 - index); if (s != to_string(stol(s))) continue; int now = stol(s); dfs(rt,num,i + 1,sofar + "+" + s,cur + now,"+",now); dfs(rt,num,i + 1,sofar + "-" + s,cur - now,"-",now); if (op == "-") { dfs(rt,num,i + 1,sofar + "*" + s,cur + val - val * now,op,val * now); }else if (op == "+") { dfs(rt,num,i + 1,sofar + "*" + s,cur - val + val * now,op,val * now);

Read full article from Leetcode: Day 130, #282 #286 Expression Add Operators, Walls and Gates