My C++ 183ms solution


  • 0
    X
    vector<string> addOperatorsWorker(vector<int>::const_iterator I,
                                      vector<int>::const_iterator E,
                                      const int64_t target, const char lowOpr,
                                      const int64_t low, const int64_t high) {
      vector<string> results;
      int64_t n = 0;
      for (auto i = I; i < E; ++i) {
        // Prevent "00...0" and "0x..x":
        if (i != I && *I == 0)
          continue;
    
        n = n * 10LL + *i;
        int64_t k = (lowOpr == '+') ? (low + n * high) : (low - n * high);
        if (i == E - 1) {
          if (target == k)
            results.push_back(to_string(n));
        } else {
          // For +/-, compute the current accumulated result.
          // Reset the high-precedence operand.
          for (auto &&r : addOperatorsWorker(i + 1, E, target, '+', k, 1))
            results.push_back(to_string(n) + '+' + r);
          for (auto &&r : addOperatorsWorker(i + 1, E, target, '-', k, 1))
            results.push_back(to_string(n) + '-' + r);
    
          // For multiplication, just carry over low-precedence accumulated result.
          // But, compute the hig-precedence operand now.
          for (auto &&r : addOperatorsWorker(i + 1, E, target, lowOpr, low, n * high))
            results.push_back(to_string(n) + '*' + r);
        }
      }
    
      return results;
    }
    
    vector<string> addOperators(string num, int target) {
      if (num.length() == 0)
        return {};
    
      // Expand to a digit vector.
      vector<int> N;
      for (char c : num)
        N.push_back(c - '0');
    
      // "+ 0" and "* 1" for the starting condition; doesn't alter the value.
      return addOperatorsWorker(N.cbegin(), N.cend(), target, '+', 0, 1);
    }
    

    The basic idea is (1) call recursively from the left to right; (2) concatenate operands (e.g., gluing 1 and 2 into 12). One caveat is disregarding 000...0 and 0x..z cases.

    The challenge is +, -, and * are left associative. We cannot simply take the result of the right hand side. To keep the left associativity, I'm passing two intermediate results: (1) low-precedence result; (2) high-precedence result.

    Regarding the final result building, I didn't pass vector<string> and string. Contrary to intuition, returning sub-results of vector<string> and using for yield better performance. I used && to eliminate any copy of sub results.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.