leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0282.cpp (1439B)

      1 class Solution {
      2     vector<string> res;
      3 
      4     vector<long long> operan;
      5     vector<char> operat;
      6 
      7     void rec(long long target, const string &num, int start, long long total, long long prev) {
      8         if (start == size(num)) {
      9             if (total != target) return;
     10 
     11             res.push_back(to_string(operan[0]));
     12             for (int i = 0; i < size(operat); i++) {
     13                 res.back() += operat[i] + to_string(operan[i + 1]);
     14             }
     15 
     16             return;
     17         }
     18 
     19         operan.push_back(-1);
     20         operat.push_back('_');
     21         for (long long i = start, crnt = 0; i < size(num); i++) {
     22             operan.back() = crnt = crnt * 10 + num[i] - '0';
     23 
     24             operat.back() = '+';
     25             rec(target, num, i + 1, total + crnt, crnt);
     26 
     27             operat.back() = '-';
     28             rec(target, num, i + 1, total - crnt, -crnt);
     29 
     30             operat.back() = '*';
     31             rec(target, num, i + 1, total + prev * (crnt - 1), prev * crnt);
     32 
     33             if (num[start] == '0') break;
     34         }
     35         operan.pop_back();
     36         operat.pop_back();
     37     }
     38 
     39   public:
     40     vector<string> addOperators(const string &num, int target) {
     41 
     42         operan.push_back(-1);
     43         for (long long i = 0, crnt = 0; i < size(num); i++) {
     44             operan.back() = crnt = crnt * 10 + num[i] - '0';
     45             rec(target, num, i + 1, crnt, crnt);
     46 
     47             if (num[0] == '0') break;
     48         }
     49 
     50         return res;
     51     }
     52 };