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

Example:

Input:"25525511135"Output:["255.255.11.135", "255.255.111.35"]

给定一组数字组成的字符串，要求输出所有的ip地址的可能。

IP地址一共有4位，每位由1-3个数字构成，范围是0-255，若某位是0，只能是“0”，而不能是“00”“000”。

public:

    vector<string> restoreIpAddresses(string s) {             

        vector<string> res;

        restore(s, 4, "", res);

        return res;

    }

    void restore(string s, int k, string out, vector<string> &res){

        if(k == 0){

            if(s.empty()) res.push_back(out);

        }

        else{

            for(int i=1; i<=3; i++){

                if(s.size() >= i && isValid(s.substr(0, i))){

                    if(k == 1) restore(s.substr(i), k-1, out + s.substr(0, i), res);

                    else restore(s.substr(i), k-1, out + s.substr(0, i) + ".", res);

                }

            }

        }       

    }

    bool isValid(string s){

        if(s.empty() || (s.size() >1 && s[0] == '0')) return false;

        int res = atoi(s.c_str());

        if(res>=0 && res<= 255) return true;

        return false;

    }