Restore IP Addresses

Restore IP Addresses

Description:

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

Example

Given “25525511135”, return
[
  ”255.255.11.135”,
  ”255.255.111.35”
]

分析：

思路：

Code:

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    /**
     * @param s the IP string
     * @return All possible valid IP addresses
     */
    vector<string> restoreIpAddresses(string& s) {
        // Write your code here
        vector<string> res;
        getRes(s, "", res, 4);
        
        return res;
    }
    
    bool valid(string s) {
        if (s.size() == 3 && (atoi(s.c_str()) > 255 || atoi(s.c_str()) == 0)) {
            return false;
        }
        if (s.size() == 3 && s[0] == '0') {
            return false;
        }
        if (s.size() == 2 && atoi(s.c_str()) == 0) {
            return false;
        }
        if (s.size() == 2 && s[0] == '0') {
            return false;
        }
        
        return true;
    }
    
    void getRes(string s, string r, vector<string> &res, int k){
        if(k == 0) {
            if (s.empty()) {
                res.push_back(r);
            }
            return;
        }
        else {
            for(int i = 1; i <= 3; i++) {
                if (s.size() >= i && valid(s.substr(0,i))) {
                    if (k == 1) {
                        getRes(s.substr(i), r + s.substr(0,i), res, k-1);
                    }
                    else {
                        getRes(s.substr(i), r + s.substr(0,i) + ".", res, k-1);
                    }
                }
            }
        }
    }
};