本题涉及下面四个难点：

• 如何模拟切割线
• 切割问题中递归如何终止
• 递归循环中如何截取子串
• 如何判断回文

问：如何模拟切割线？

答：递归 dfs 中需要传入 start 参数，表示下一轮递归遍历的起始位置，该 start 就是切割线。

问：切割问题中递归如何终止？

答：当 dfs 传入的 start 参数已经大于字符串 s 的长度时，说明已经找到了一组分割方案。终止条件如下代码所示：

if start >= len(s) {
    temp := make([]string, len(path))
    copy(temp, path)
    result = append(result, temp)
    return
}

问：递归循环中如何截取子串？

答：在递归循环 for (int i := start; i < len(s); i++) 中，对于起始位置 start 来说，[start, i] 就是要截取的子串。具体逻辑如下：

for i := start; i < len(s); i++ {
    str := s[start:i+1]           // 截取需要判断是否为回文的子串
    if isTrue(str) {
        path = append(path, str)
        dfs(s, i+1)               // 不能重复切割，所以传入 i+1
        path = path[:len(path)-1]
    }
}

问：如何判断回文？

答：判断一个字符串是否为回文字符串，可以使用双指针法。一个指针从前向后，一个指针从后向前，如果前后指针所指向的元素是相等的，就是回文字符串了。代码逻辑如下：

func isTrue(str string) bool {
    for i, j := 0, len(str)-1; i < j; i, j = i+1, j-1 {
        if str[i] != str[j] {
            return false
        }
    }
    return true
}

时间复杂度：O(n*2^n)

空间复杂度：O(n^2)

完整代码如下：

var (
	path   []string
	result [][]string
)

func partition(s string) [][]string {
	path = []string{}
	result = [][]string{}
	dfs(s, 0)
	return result
}

func dfs(s string, start int) {
	if start >= len(s) {
		temp := make([]string, len(path))
		copy(temp, path)
		result = append(result, temp)
		return
	}

	for i := start; i < len(s); i++ {
        str := s[start:i+1]
		if isTrue(str) {
			path = append(path, str)
			dfs(s, i+1)
			path = path[:len(path)-1]
		}
	}
}

func isTrue(s string) bool {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		if s[i] != s[j] {
			return false
		}
	}
	return true
}

本题涉及以下几个难点：

• 如何模拟切割线
• 切割问题中递归如何终止
• 递归循环中如何截取子串
• 判断子串是否合法

问：如何模拟切割线？

答：与 131.分割回文串一样，需要 start 记录下一层递归分割的起始位置。

问：切割问题中递归如何终止？

答：与 131.分割回文串不同的是，IP 确定是 4 段式。因此要以分割的段数作为终止条件，切割线切到最后是作为收集结果的条件。代码如下：

if len(path) == 4 {         // 分割段数为 4 时作为终止条件
    if start >= len(s) {    // 切割线切到最后要收集结果
        ip := strings.Join(path, ".")
        result = append(result, ip)
    }
    return
}

问：递归循环中如何截取子串？

答：有 131.分割回文串一样，在 for i := start; i < len(s); i++ 循环中 [start, i] 这个区间就是截取的子串，需要判断这个子串是否合法。代码如下：

for i := start; i < len(s); i++ {
    str := s[start:i]
    // 判断子串是否合法的逻辑
}

问：判断子串是否合法？

答：子串中是以 0 开头的且大于 1 位数字组成的不合法、子串数值小于 0 或 大于 255 的不合法。与递归循环中如何截取子串结合，代码如下：

for i := start; i < len(s); i++ {
    str := s[start:i]
    if i > start && s[start] == '0' {     // 判断以0开头且位数大于1的子串,视为不合法
        break
    }
    num, _ := strconv.Atoi(str)            // 将数值类型字符串转成int类型
    if num >= 0 && num <= 255 {            // 判断数值小于0或大于255的子串,视为不合法
        path = append(path, str)
        dfs(s, i+1)
        path = path(:len(path)-1)
    }
}

时间复杂度：O(3^4)，IP地址最多包含四个数字，每个数字最多有三种分割方法，所以搜索树的最大深度是4，每个节点最多有3个子节点（即一层最多三个节点）。

空间复杂度：O(n)

完整代码如下：

var (
    path []string
    result []string
)

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

func dfs(s string, start int) {
    if len(path) == 4 {
        if start >= len(s) {
            ip := strings.Join(path, ".")
            result = append(result, ip)
        }
        return 
    }

    for i := start; i < len(s); i++ {
        if i > start && s[start] == '0' {
            break
        }
        str := s[start:i+1]
        num, _ := strconv.Atoi(str)
        if num >= 0 && num <= 255 {
            path = append(path, str)
            dfs(s, i+1)
            path = path[:len(path)-1]
        }
    }
}