C++ 4 ms Recursive Backtracking


  • 0
    H

    Be noticed that backtracking has the nature of stack. Recursive call has the nature of stack.

    To best solve a back tracking problem, we should use recursive call.

    1. Making each decision and delete the conflict value from the value set, call recursive function.
    2. Parameter passing the remain valid solution value set, make sure it is copy not reference.
    3. Add an accumulated valid result at return or via reference.

    class Solution {

    public:
    vector<string> restoreIpAddresses(string s) {
        vector<string > ans;
        int len = s.size();
        if (len < 4 || len > 12) return ans;
        restoreIpAddresses(ans,s,0,"", 1);
        return ans;
    }
    void restoreIpAddresses(vector<string> &ans, string &s,int pos, string s_ans, int dep){
        int len = s.size();
        for (int i=1; i<4; ++i){
            if (i+pos > len) break;
            string temp_s = s.substr(pos,i);
            int temp_i = stoi(temp_s,NULL);
            if (temp_i < 256 && (i<2 || temp_i > 9) && (i<3 || temp_i >99)){
    	        if (dep != 4) {// not reaches the dep 4 yet
    	            restoreIpAddresses(ans,s,pos+i,s_ans + temp_s + '.' , dep + 1);
    	        } else if (i+pos == len) {
    	            ans.push_back(s_ans + temp_s); //meet a final answer
    	        }
            }
        }
    }
    

    };


Log in to reply
 

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