康瑞部落

Restore IP Addresses

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

For example:
Given "25525511135",

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

解题思路：

注意到ip地址分成四部分，每部分0<=ip<=25，字符串的表示中，还不能是010这种形式。有两种办法，第一种枚举法，枚举每一部分的IP形式，代码如下：

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        int len = s.length();
        vector<string> result;
        if(len>12 || len < 4){
            return result;      //不满足的情况
        }
        //枚举法，最多C(n-1, 3)中情况
        for(int i1=1; i1 < 4 && i1 <= len - 3; i1++){
            string ip1 = s.substr(0, i1);
            if(checkIP(ip1)){
                for(int i2 = i1 + 1; i2 < i1 + 4 && i2 <= len - 2; i2++){
                    string ip2 = s.substr(i1, i2 - i1);
                    if(checkIP(ip2)){
                        for(int i3 = i2 + 1; i3 < i2 + 4 && i3 <= len - 1; i3++){
                            string ip3 = s.substr(i2, i3 - i2);
                            if(checkIP(ip3)){
                                string ip4 = s.substr(i3);
                                if(checkIP(ip4)){
                                    result.push_back(ip1 + "." + ip2 + "." + ip3 + "." + ip4);
                                }
                            }
                        }
                    }
                }
            }
        }
        
        return result;
    }
private:
    bool checkIP(string s){
        int len = s.length();
        if(len > 3 || len == 0){
            return false;
        }
        //高位不能为0
        if(s[0] == '0' && len>1){
            return false;
        }
        //不能超过255
        int iNumber = 0;
        int base = 1;
        for(int i=len-1; i>=0; i--){
            iNumber += base * (s[i] - '0');
            base *= 10;
        }
        if(iNumber>255){
            return false;
        }
        return true;
    }
};

这里注意一个问题，每个地方都枚举太麻烦了，倘若有100个ip块，岂不是要手动验证100次？太麻烦了！可以想到回溯法，通过递归进行回溯，具体要解析多少个ip块，通过参数指定。代码如下：

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        int len = s.length();
        vector<string> result;
        if(len>12 || len < 4){
            return result;      //不满足的情况
        }
        partIP(result, 0, 4, "", s);
        
        return result;
    }
private:
    void partIP(vector<string>& result, int startIndex, int leftNumber, string tempResult, string& s){
        int len = s.length();
        if(leftNumber <= 0){
            return;
        }
        if(len - startIndex < leftNumber){
            return;
        }
        for(int i=startIndex + 1; i< startIndex + 4 && i <= len ; i++){
            string ip = s.substr(startIndex, i - startIndex);
            if(checkIP(ip)){
                if(leftNumber == 1 && i == len){
                    result.push_back(tempResult + ip);
                }else{
                    partIP(result, i, leftNumber - 1, tempResult + ip + ".", s);
                }
            }else{
                break;
            }
        }
    }
    bool checkIP(string s){
        int len = s.length();
        if(len > 3 || len == 0){
            return false;
        }
        //高位不能为0
        if(s[0] == '0' && len>1){
            return false;
        }
        //不能超过255
        int iNumber = 0;
        int base = 1;
        for(int i=len-1; i>=0; i--){
            iNumber += base * (s[i] - '0');
            base *= 10;
        }
        if(iNumber>255){
            return false;
        }
        return true;
    }
};