Restore IP Addresses

LeetCode #93

Description:

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Idea:

最好用Backtrack的方法，因为要给出所有的解，这样就不用复制所有的中间结果。

这题的backtrack需要考虑两种情况，一个是'.',另一个是当前的sub string段。

Code:

Method 1 Backtrack的做法。中间结果用一个string存，每次递归用同一个string。

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        string ip;
        DFS(s, 0, 0, ip, result);
        return result;
    }

    void DFS(const string& s, int loc, int step, string& ip, vector<string>& result){
        if(loc==s.size() && step==4){
            result.push_back(ip.substr(0, ip.size()-1));
            return;
        }

        if(s.size() - loc > (4-step)*3)
            return;

        if(s.size() - loc < (4-step))
            return;

        int num=0;
        int sub_len=0;
        for(int i=loc; i<loc+3; ++i){
            num = num*10 + (s[i] - '0');

            if(num<=255){ // 当前结点合法，则继续往下递归
                sub_len++;
                ip += s[i];
                ip += '.';
                // cout<<"step "<<step<<' '<<ip<<' '<<num<<endl;
                DFS(s, i+1, step+1, ip, result);
                ip.pop_back();  // Backtrack '.'
            }
            if(num==0) break; // 不允许前缀 0，但允许单个 0
        }

        ip.erase(ip.size()-sub_len, sub_len); // Backtrack 当前的sub string
    }
};

Method 2 不是backtrack的做法。中间结果用一个string存，每次递归用复制这个string。

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        string ip;
        DFS(s, 0, 0, ip, result);
        return result;
    }

    void DFS(string s, int loc, int step, string ip, vector<string>& result){
        if(loc==s.size() && step==4){
            result.push_back(ip.substr(0, ip.size()-1));
            return;
        }

        if(s.size() - loc > (4-step)*3)
            return;
        if(s.size() - loc < (4-step))
            return;

        int num=0;
        for(int i=loc; i<loc+3; ++i){
            num = num*10 + (s[i] - '0');

            if(num<=255){
                ip += s[i];
                DFS(s, i+1, step+1, ip+'.', result);
            }
            if(num==0) break;
        }

    }
};