## 题目 #

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

Example:

``````Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
``````

## 解题思路 #

• DFS 深搜
• 需要注意的点是 IP 的规则，以 0 开头的数字和超过 255 的数字都为非法的。

## 代码 #

``````
package leetcode

import (
"strconv"
)

if s == "" {
return []string{}
}
res, ip := []string{}, []int{}
dfs(s, 0, ip, &res)
return res
}

func dfs(s string, index int, ip []int, res *[]string) {
if index == len(s) {
if len(ip) == 4 {
*res = append(*res, getString(ip))
}
return
}
if index == 0 {
num, _ := strconv.Atoi(string(s[0]))
ip = append(ip, num)
dfs(s, index+1, ip, res)
} else {
num, _ := strconv.Atoi(string(s[index]))
next := ip[len(ip)-1]*10 + num
if next <= 255 && ip[len(ip)-1] != 0 {
ip[len(ip)-1] = next
dfs(s, index+1, ip, res)
ip[len(ip)-1] /= 10
}
if len(ip) < 4 {
ip = append(ip, num)
dfs(s, index+1, ip, res)
ip = ip[:len(ip)-1]
}
}
}

func getString(ip []int) string {
res := strconv.Itoa(ip[0])
for i := 1; i < len(ip); i++ {
res += "." + strconv.Itoa(ip[i])
}
return res
}

``````

Apr 8, 2023