1. 题目描述

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)

2. 解题思路

拿到这道题目其实一点思路都没有， 没办法只能将他分成4个部分， 通过三层循环来划分各个部分。代码写出来自己都觉得很丑陋。。。

3. code

3.1 20160413

需要注意一些特殊情形：part 长度为 0， part 值大于 255， part 值不符合数学意义 （”00”）

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        int len = s.size();
        string part1, part2, part3, part4;
        vector<string> res;
        for (int i = 1; i <= min(3, len); i++){
            part1 = s.substr(0, i);
            int remain_size = len - part1.size();
            if ((part1.size() == 0 || stoi(part1) > 255) || (remain_size < 3 || remain_size > 3 * 3) || part1 != to_string(stoi(part1)))
                continue;
            for (int j = i + 1; j <= min(i + 3, len); j++){
                part2 = s.substr(i, j - i);
                remain_size = len - part1.size() - part2.size();
                if ((part2.size() == 0 || stoi(part2) > 255) || (remain_size < 2 || remain_size > 3 * 2) || part2 != to_string(stoi(part2)))
                    continue;
                for (int k = j + 1; k <= min(j + 3, len); k++){
                    part3 = s.substr(j, k - j);
                    part4 = s.substr(k);
                    if (part3.size() == 0 || stoi(part3) > 255 || part4.size() == 0 || stoi(part4) > 255 || part3 != to_string(stoi(part3))
                        || part4 != to_string(stoi(part4)))
                        continue;

                    string tmp = part1 + "." + part2 + "." + part3 + "." + part4;
                    res.push_back(tmp);
                }
            }
        }

        return res;
    }
};

3.2 20160414 DFS

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        helper(s, 0, 0, "", res);
        return res;
    }

private:
    void helper(string s, int start, int level, string cur, vector<string> & res){
        if (level == 4 && cur.size() == s.size() + 4){
            cur.pop_back();
            res.push_back(cur);
            return;
        }

        if (s.size() - start < 4 - level || s.size() - start > 3 * (4 - level))
            return;

        int num = 0;
        for (int i = start; i < min(start + 3, int(s.size())); i++){
            num = 10 * num + s[i] - '0';
            cur += s[i];
            int pos = cur.rfind('.');
            string last = cur.substr(pos + 1);
            if (last != to_string(num))
                break;

            if (num < 256)
                helper(s, i + 1, level + 1, cur + '.', res);
        }
    }
};

4. 大神解法

4.1 demo1

这个思路和我们的差不多

public class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<String>();
        int len = s.length();
        for(int i = 1; i<4 && i<len-2; i++){
            for(int j = i+1; j<i+4 && j<len-1; j++){
                for(int k = j+1; k<j+4 && k<len; k++){
                    String s1 = s.substring(0,i), s2 = s.substring(i,j), s3 = s.substring(j,k), s4 = s.substring(k,len);
                    if(isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)){
                        res.add(s1+"."+s2+"."+s3+"."+s4);
                    }
                }
            }
        }
        return res;
    }
    public boolean isValid(String s){
        if(s.length()>3 || s.length()==0 || (s.charAt(0)=='0' && s.length()>1) || Integer.parseInt(s)>255)
            return false;
        return true;
    }
}

4.2 DFS

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        string ip;
        dfs(s,0,0,ip,result); //paras:string s,start index of s,step(from0-3),intermediate ip,final result
        return result;
    }
    void dfs(string s,int start,int step,string ip,vector<string>& result){
        if(start==s.size()&&step==4){
            ip.erase(ip.end()-1); //remove the last '.' from the last decimal number
            result.push_back(ip);
            return;
        }
        if(s.size()-start>(4-step)*3) return;
        if(s.size()-start<(4-step)) return;
        int num=0;
        for(int i=start;i<start+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;
        }
    }
};