0093. 复原IP地址.md

93. 复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]

code

带预剪枝的深搜

class Solution {
public:
    vector<string> ans;
    int len;
    int split[3] = {0};
    string str;
    vector<string> restoreIpAddresses(string s) {
        len = s.size();
        str = s;
        dfs(0);
        return ans;
    }
    void dfs(int num){
        if(num == 3){
            if(valid(split[2], len))
                push_string();
            return;
        }
        int start = num == 0 ? 0 : split[num-1];
        for(int i=1; i<=3; i++){
            if(!valid(start, start+i))
                return;
            split[num] = start + i;
            dfs(num+1);
        }
    }
    bool valid(int left, int right){
        if(right > len || right -left > 3 || left == right || str[left] == '0' && right > left+1)
            return false;
        int number = 0;
        for(int i=left; i<right; i++)
            number = number*10+str[i]-'0';
        if(number > 255)
            return false;
        return true;
    }
    void push_string(){
        string tmp;
        for(int i=0, j=0; i<len; i++){
            if(j < 3 && i == split[j]){
                tmp.push_back('.');
                j++;
            }
            tmp.push_back(str[i]);
        }
        ans.push_back(tmp);
    }
};