仰望星空

位我上者，灿烂星空；道德律令，在我心中。

0%

复原IP地址

发表于 更新于 分类于 ，
本文字数： 2.2k 阅读时长 ≈ 2 分钟

【道德经·第二十六章】 重为轻根，静为躁君。是以君子终日行不离辎重，虽有荣观，燕处超然。奈何万乘之主，而以身轻天下？轻则失根，躁则失君。

93. 复原 IP 地址

有效IP地址 正好由四个整数（0到255，不含前导 0），整数之间用 ‘.’ 分隔。

示例 1：

1
2
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

1
2
输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

1
2
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

  • 1 <= s.length <= 20
  • s仅由数字组成

回溯法一:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<string> restoreIpAddresses(string s) {
    vector<string> res;
    helper(s, res, "", 0);
    return res;
}

void helper(string s, vector<string>& res, string out, int n) {
    if(n == 4) {
        if(s.empty()) res.push_back(out);
        return;
    }

    for(int k = 1; k < 4; k++) {
        if(s.size() < k) break;
        int val = stoi(s.substr(0, k));
        if(val>255 || k!=std::to_string(val).size()) continue;
        helper(s.substr(k), res, out+s.substr(0, k)+(n==3 ? "":"."), n+1);
    }
}

回溯法二:

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
void dfs(string& s, vector<string>& res, string& cur, int step, int index) {
    if(step == 4) {
        if(index != s.size()) return;
        res.push_back(cur);
        return;
    }

    string t1 = "";
    for(int i = index; i<index+3 && i<s.size(); i++) {
        t1 += s[i];
        int num = stoi(t1);
        string t2 = cur;
        if(num<=255 && (t1.size()==1 || t1[0]!='0')) {
            cur += t1;
            if(step != 3) cur += ".";
            dfs(s, res, cur, step+1, i+1);
            cur = t2;
        }
    }
}

vector<string> restoreIpAddresses(string s) {
    vector<string> res;
    string cur;
    dfs(s, res, cur, 0, 0);
    return res;
}

迭代法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
vector<string> restoreIpAddresses(string s) {
    vector<string> res;
    for(int a = 1; a < 4; a++)
    for(int b = 1; b < 4; b++)
    for(int c = 1; c < 4; c++)
    for(int d = 1; d < 4; d++) 
        if(a+b+c+d == s.size()) {
            int va = stoi(s.substr(0, a));
            int vb = stoi(s.substr(a, b));
            int vc = stoi(s.substr(a+b, c));
            int vd = stoi(s.substr(a+b+c, d));
            if(va<=255 && vb<=255 && vc<=255 && vd<=255) {
                string t = to_string(va) + "." + to_string(vb) + "." + to_string(vc) + "." + to_string(vd);
                if(t.size() == s.size()+3) res.push_back(t);
            }
        }

    return res;
    
}

位我上者，灿烂星空；道德律令，在我心中。