Restore IP Addresses (Medium)

Description

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)

Analysis

枚举每个位置的长度。只能在1-3之间。另外如果取了i长度之后，后面部分超过或不够可解长度则不再进行

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//C++
class Solution {
    vector<string> ans;
    void dfs(int st,int total,string s,string t){
        if(total==4){
            //cout<<t<<endl;
            ans.push_back(t);
            return;
        }
        if(st!=0)   t+=".";

        for(int i=1;i<=3;i++){
            string x;
            int num = 0;
            for(int j=0;j<i;j++){
                x+=s[st+j];
                num = num*10+s[st+j]-'0';
            }
            if(num>255)
                return;
            if(i>1&&x[0]=='0')
                continue;
            int len = s.length();
            if((len-st-i)<(3-total)||(len-st-i)>3*(3-total))
                continue;
            dfs(st+i,total+1,s,t+x);
        }
    }
public:
    vector<string> restoreIpAddresses(string s) {
        int len = s.length();
        if(len<4||len>12)
            return ans;
        dfs(0,0,s,"");
        return ans;
    }
};