93. 复原 IP 地址

题目描述

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

示例 1：

输入：s = “25525511135”
输出：[“255.255.11.135”,“255.255.111.35”]

示例 2：

输入：s = “0000”
输出：[“0.0.0.0”]

示例 3：

输入：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
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


func restoreIpAddresses(s string) []string {
    if len(s) < 4 || len(s) > 16 {
        return []string{}
    }
    getNum := func(i, j int) int {
        res := 0
        for i <= j {
            res = res*10 + int(s[i]-'0')
            i++
        }
        return res
    }
    n := len(s)

    var ans []string
    var tmp []string
    var backtracking func(segId, segStart int)
    backtracking = func(segId, segStart int) {
        if segStart >= n {
            if segId == 4 {
                ans = append(ans, strings.Join(tmp, "."))
            }
            return
        } else if segId > 3 {
            // pruning operation in backtracking algorithm
            // segStart < n && segId > 3
            return
        } else {
            // segStart < n && segId <= 3
            if s[segStart] == '0' {
                tmp = append(tmp, "0")
                backtracking(segId+1, segStart+1)
                tmp = tmp[:len(tmp)-1]
            } else {
                for j := segStart; j < n; j++ {
                    if getNum(segStart, j) > 255 {
                        break
                    }
                    tmp = append(tmp, s[segStart:j+1])
                    backtracking(segId+1, j+1)
                    tmp = tmp[:len(tmp)-1]
                }
            }
        }

    }
    backtracking(0, 0)
    return ans
}

官方题解如下：

 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


const SEG_COUNT = 4

var (
    ans []string
    segments []int
)

func restoreIpAddresses(s string) []string {
    segments = make([]int, SEG_COUNT)
    ans = []string{}
    dfs(s, 0, 0)
    return ans
}

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

    // 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
    if segStart == len(s) {
        return
    }
    // 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
    if s[segStart] == '0' {
        segments[segId] = 0
        dfs(s, segId + 1, segStart + 1)
    }
    // 一般情况，枚举每一种可能性并递归
    addr := 0
    for segEnd := segStart; segEnd < len(s); segEnd++ {
        addr = addr * 10 + int(s[segEnd] - '0')
        if addr > 0 && addr <= 0xFF {
            segments[segId] = addr
            dfs(s, segId + 1, segEnd + 1)
        } else {
            break
        }
    }
}