解题思路

这题考点就是剪枝

  1. 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案

  2. 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯

  3. 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        # 4 * 3 = 12
        if len(s) > 12: return []
        result = []
        def backtracking(startIndex: int, temp: list[str]):
            if len(temp) == 4:
                if startIndex >= len(s):
                    result.append(".".join(temp))
                return
            c = ""
            for i in range(startIndex, startIndex + 3):
                if i >= len(s): return
                c += s[i]
                if len(c) > 1 and c[0] == '0': return
                if 0 <= int(c) <= 255:
                    temp.append(c)
                    backtracking(i + 1, temp)
                    temp.pop()
        
        backtracking(0, [])
        return result

C++

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
53
54
55
class Solution {
private:
    static constexpr int SEG_COUNT = 4;

private:
    vector<string> ans;
    vector<int> segments;

public:
    void dfs(const string& s, int segId, int segStart) {
        // 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
        if (segId == SEG_COUNT) {
            if (segStart == s.size()) {
                string ipAddr;
                for (int i = 0; i < SEG_COUNT; ++i) {
                    ipAddr += to_string(segments[i]);
                    if (i != SEG_COUNT - 1) {
                        ipAddr += ".";
                    }
                }
                ans.push_back(move(ipAddr));
            }
            return;
        }

        // 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
        if (segStart == s.size()) {
            return;
        }

        // 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
        if (s[segStart] == '0') {
            segments[segId] = 0;
            dfs(s, segId + 1, segStart + 1);
        }

        // 一般情况，枚举每一种可能性并递归
        int addr = 0;
        for (int segEnd = segStart; segEnd < s.size(); ++segEnd) {
            addr = addr * 10 + (s[segEnd] - '0');
            if (addr > 0 && addr <= 0xFF) {
                segments[segId] = addr;
                dfs(s, segId + 1, segEnd + 1);
            } else {
                break;
            }
        }
    }

    vector<string> restoreIpAddresses(string s) {
        segments.resize(SEG_COUNT);
        dfs(s, 0, 0);
        return ans;
    }
};

Go

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
var result []string

func restoreIpAddresses(s string) []string {
    result = []string{}
    backtracking(s, 0, []string{})
    return result

}

func backtracking(s string, startIndex int, temp []string) {
    if len(temp) == 4 {
        if startIndex >= len(s) {
            result = append(result, strings.Join(temp, "."))
        }
        return
    }

    c := ""
    for i := startIndex; i < startIndex + 3; i++ {
        if i == len(s) {return}
        c += string(s[i])
        if len(c) > 1 && c[0] == '0' {return}
        num, _ := strconv.Atoi(c)
        if num >= 0 && num <= 255 {
            temp = append(temp, c)
            backtracking(s, i + 1, temp)
            temp = temp[:len(temp) - 1]
        }
    }
}