C++ DFS solution with explanation (similar to word break)


  • 0

    Note that the binary operator options here are '+', '-' and '*', which means:

    1. You cannot put any operator before first number.
    2. Be careful when you put '*' for DFS because it has higher priority any '+' and '-'.

    The following variables will be enough for to track DFS process (assuming we have num[i] to process next):

    • cv: evaluation so far for previous string num[0:i)
    • pmv: evaluation of previous multiple value (e.g., "3-5*6" -> pmv = -5*6=-30)
    • r: evaluation string so far for previous string num[0:i)
        vector<string> res;
        string s; // copy of num
        int t; // copy of target
        
        vector<string> addOperators(string num, int target) {
            s = num, t = target;
            dfs(0, 0, 0, "");
            return res;
        }
        
        // i: current position to process
        // cv: current evaluation of s[0:i)
        // pmv: previous multiplied value before i
        // r: current evaluation string
        void dfs(int i, long cv, long pmv, string r) {
            if (i == s.size() and cv == t) {
                res.push_back(r);
                return;
            }
            // process s.substr(i, L) for different length as current number
            for (int L = 1; L <= s.size() - i; ++L) {
                if (L > 1 and s[i] == '0') break; // "0*" is invalid number
                string cs = s.substr(i, L);            
                long csv = stol(cs);
                if (i == 0) // cannot put binary operator before first number
                    dfs(L, csv, csv, cs);
                else {
                    dfs(i+L, cv+csv,         csv,     r+"+"+cs); // +
                    dfs(i+L, cv-csv,         -csv,    r+"-"+cs); // -
                    dfs(i+L, cv-pmv+pmv*csv, pmv*csv, r+"*"+cs); // *
                }
            }
        }
    

Log in to reply
 

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