0093.复原 IP 地址

https://leetcode.cn/problems/restore-ip-addresses/

方法一：回溯

时间复杂度 $O(3^4 \times n)$，空间复杂度 $O(4)$。

func restoreIpAddresses(s string) []string {
	ans, n := []string{}, len(s)
	var backtrack func(seg []int, start int)
	backtrack = func(seg []int, start int) {
		if len(seg) == 4 && start == n {
			fmt.Println(seg)
			ipv4 := s[:seg[0]] + "." + s[seg[0]:seg[1]] + "." + s[seg[1]:seg[2]] + "." + s[seg[2]:]
			ans = append(ans, ipv4)
			return
		} else if start == n || len(seg) == 4 {
			return
		}
		if s[start] == '0' {
			seg = append(seg, start+1)
			backtrack(seg, start+1)
			return
		}
		digit := 0
		for i := start; i < n; i++ {
			digit = digit*10 + int(s[i]-'0')
			if digit > 0 && digit <= 255 {
				seg = append(seg, i+1)
				backtrack(seg, i+1)
				seg = seg[:len(seg)-1]
			} else {
				break
			}
		}
	}
	backtrack([]int{}, 0)
	return ans
}