Simple DFS with mutually recursive methods (C++ 26 ms)


  • 0
    D

    This depth-first search implementation avoids some of the complexity of other DFS solutions by separating the search into 3 separate methods which call one another. Three variables are used to track state: currentInt which is the current integer being constructed, currentTerm which is the current multiplied product (negative if it's being subtracted, positive if it's being added), and currentOverall which is the sum of all terms before the current one.

    class Solution {
        // Handles digits that aren't the first digit in a number, and end of string
        void dfsnum2(string& num, int i, int currentInt, int currentTerm, int currentOverall, int target, vector<string>& result) {
            if (i == num.size()) {
                if (currentOverall + currentTerm * currentInt == target) {
                    result.push_back(num);
                }
                return;
            }
            
            dfs(num, i, currentInt * currentTerm, currentOverall, target, result);
            
            if (currentInt != 0) { // If it's zero, don't add more digits
                int val = num[i] - '0';
                if (currentInt <= (numeric_limits<int>::max() - val)/10) { // Check for overflow
                    dfsnum2(num, i + 1, currentInt * 10 + val, currentTerm, currentOverall, target, result);
                }
            }
        }
        
        // Handles digits that are the first digit in a number
        void dfsnum(string& num, int i, int currentTerm, int currentOverall, int target, vector<string>& result) {
            dfsnum2(num, i + 1, num[i] - '0', currentTerm, currentOverall, target, result);
        }
        
        // Handles operators
        void dfs(string& num, int i, int currentTerm, int currentOverall, int target, vector<string>& result) {
            num.insert(i, "+");
            dfsnum(num, i+1, 1, currentOverall + currentTerm, target, result);
            num.erase(i, 1);
            
            num.insert(i, "-");
            dfsnum(num, i+1, -1, currentOverall + currentTerm, target, result);
            num.erase(i, 1);
            
            num.insert(i, "*");
            dfsnum(num, i+1, currentTerm, currentOverall, target, result);
            num.erase(i, 1);
        }
        
    public:
        vector<string> addOperators(string num, int target) {
            vector<string> result;
            if (num.length() == 0) {
                if (target == 0) result.push_back("");
            } else {
                dfsnum(num, 0, 1, 0, target, result);
            }
            return result;
        }
    };
    

Log in to reply
 

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