Clean C++ DFS solution beating 96%


  • 0
    C

    Base on Basic Calculator II, the handling for * is that, we keep a prev variable to keep track of the previous addition or subtraction operation, when we what to use * operator, we can do:

    current_sum = current_sum - prev + prev * operand,
    prev = prev * operand

    Then we just need to use DFS to enumerate all possibilities of adding multiplication, addition, subtraction operators at each possible positions.

    One thing we need to pay attention is that if the current number has more than 1 digits, and it's starting with a 0, then this is not a valid case.

        vector<string> addOperators(string num, int target) {
            string path;
            vector<string> result;
            dfs(num, 0, 0, target, 0, path, result);
            return result;
        }
        
        void dfs(const string& num, int pos, long long sum, int target, long long prev, string& path, vector<string>& result) {
            if (pos >= num.size()) {
                if (sum == target) result.push_back(path);
                return;
            }
            
            long long left = 0;
            int size = path.size();
            string buffer;
            for (int i=pos; i<num.size(); i++) {
                left = left * 10 + num[i] - '0';
                buffer.push_back(num[i]);
                if (pos == 0) {
                    path += buffer;
                    dfs(num, i+1, sum+left, target, left, path, result);
                    path.resize(size);
                } else {
                    path += "+";
                    path += buffer;
                    dfs(num, i+1, sum+left, target, left, path, result);
                    path.resize(size);
                    
                    path += "-";
                    path += buffer;
                    dfs(num, i+1, sum-left, target, -left, path, result);
                    path.resize(size);
                    
                    path += "*";
                    path += buffer;
                    dfs(num, i+1, sum-prev+prev*left, target, prev*left, path, result);
                    path.resize(size);
                }
                if (num[pos] == '0') break;
            }
        }
    

Log in to reply
 

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