Create 282_Expression_Add_Operators.cpp (qiyuangong#32)

bhanu1131 · web-flow · commit bb21f19083c4 · 2020-10-28T22:32:45.000+08:00
* Create 282_Expression_Add_Operators.cpp, by @bhanu1131
diff --git a/cpp/282_Expression_Add_Operators.cpp b/cpp/282_Expression_Add_Operators.cpp
@@ -0,0 +1,53 @@
+class Solution {
+public:
+    vector<string> addOperators(string num, int target) {
+        vector<string> result;
+        if (num.size() == 0) return result;
+        findSolution(num, target, result, "", 0, 0, 0, ' ');
+        return result;        
+    }
+
+    //DFS algorithm
+    void findSolution(const string &num, const int target,
+                vector<string>& result, 
+                string solution,
+                int idx,
+                long long val,
+                long long prev,
+                char preop )
+    {
+
+        if (target == val && idx == num.size()){
+            result.push_back(solution);
+            return;
+        }
+        if (idx == num.size()) return;
+
+        string n;
+        long long v=0;
+        for(int i=idx; i<num.size(); i++) {
+            //get rid of the number which start by "0"
+            //e.g.  "05" is not the case.
+            if (n=="0") return;
+
+            n = n + num[i];
+            v = v*10 + num[i]-'0';
+
+            if (solution.size()==0){ 
+                findSolution(num, target, result, n, i+1, v, 0, ' ');
+            }else{
+                // '+' or '-' needn't to adjust the priority
+                findSolution(num, target, result, solution + '+' + n, i+1, val+v, v, '+');
+                findSolution(num, target, result, solution + '-' + n, i+1, val-v, v, '-');
+                if (preop=='+') {
+                    findSolution(num, target, result, solution + '*' + n, i+1, (val-prev)+prev*v, prev*v, preop);
+                }else if (preop=='-'){
+                    findSolution(num, target, result, solution + '*' + n, i+1, (val+prev)-prev*v, prev*v, preop);
+                }else {
+                    findSolution(num, target, result, solution + '*' + n, i+1, val*v, v, '*');
+                }
+            }
+        }
+
+    }
+};
