leetcode 93. 复原IP地址

题解

dfs 深度优先搜索,每次取 1~3 位为一个 ip 地址段,然后对剩下的字符串进行递归(注意地址段是否合法)

示例代码(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
31
32
33
34
35
36
37
func restoreIpAddresses(s string) []string {
res := make([]string, 0)
dfs(s, []string{}, &res)
return res
}

func dfs(s string, arr []string, res *[]string) {
n := len(s)
if s != "" && len(arr) == 4 {
return
}
if s == "" && len(arr) == 4 {
*res = append(*res, strings.Join(arr, "."))
return
}
for i := 0; i < 3 && i < n; i++ {
if isLess(s[:i+1], "255") && isLegal(s[:i+1]) {
dfs(s[i+1:], append(arr, s[:i+1]), res)
}
}
}

func isLess(a, b string) bool {
a1, _ := strconv.Atoi(a)
b1, _ := strconv.Atoi(b)
if a1 <= b1 {
return true
}
return false
}

func isLegal(str string) bool {
if str[0] == '0' && len(str) > 1 {
return false
}
return true
}