93. Restore IP Addresses

發表於 | 分類於

problem

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
class Solution {
public:
    vector<string> ret;
    bool isValid(string s){
        if (s.empty() || s.size() > 3 || (s.size() > 1 && s[0] == '0')) return false;
        int res = atoi(s.c_str());
        return res <= 255 && res >= 0;
    }
    
    void dfs(string s, int k, string path){
        if(k==0){
            if(s.empty()) ret.push_back(path);
            return;
        }
        for(int i=1;i<=3;++i){
            if(s.size() >= i  && isValid(s.substr(0,i) )){
                if(k==1) dfs(s.substr(i) , k-1, path+s.substr(0,i));
                else dfs(s.substr(i), k-1, path+s.substr(0,i)+'.');
                
            }
        }
    }
    
    vector<string> restoreIpAddresses(string s) {
        dfs(s, 4, "");
        return ret;
    }
};