题目

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 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 地址。

示例 1：输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]

示例 2：输入：s = "0000" 输出：["0.0.0.0"]

示例 3：输入：s = "1111" 输出：["1.1.1.1"]

示例 4：输入：s = "010010" 输出：["0.10.0.10","0.100.1.0"]

示例 5：输入：s = "10203040" 输出：["10.20.30.40","102.0.30.40","10.203.0.40"]

提示：0 <= s.length <= 3000

s 仅由数字组成

注意：本题与主站 93 题相同

解题思路分析

1、回溯；时间复杂度O(1)，空间复杂度O(1)

var res []string

func restoreIpAddresses(s string) []string {
   res = make([]string, 0)
   if len(s) < 4 || len(s) > 12 {
      return nil
   }
   dfs(s, make([]string, 0), 0)
   return res
}

func dfs(s string, arr []string, level int) {
   if level == 4 {
      if len(s) == 0 {
         str := strings.Join(arr, ".")
         res = append(res, str)
      }
      return
   }
   for i := 1; i <= 3; i++ {
      if i <= len(s) {
         value, _ := strconv.Atoi(s[:i])
         if value <= 255 {
            str := s[i:]
            dfs(str, append(arr, s[:i]), level+1)
         }
         if value == 0 {
            // 避免出现001,01这种情况
            break
         }
      }
   }
}

2、暴力法；时间复杂度O(1)，空间复杂度O(1)

func restoreIpAddresses(s string) []string {
   res := make([]string, 0)
   if len(s) < 4 || len(s) > 12 {
      return nil
   }
   for i := 1; i <= 3 && i < len(s)-2; i++ {
      for j := i + 1; j <= i+3 && j < len(s)-1; j++ {
         for k := j + 1; k <= j+3 && k < len(s); k++ {
            if judge(s[:i]) && judge(s[i:j]) &&
               judge(s[j:k]) && judge(s[k:]) {
               res = append(res, s[:i]+"."+s[i:j]+"."+s[j:k]+"."+s[k:])
            }
         }
      }
   }
   return res
}

func judge(s string) bool {
   if len(s) > 1 && s[0] == '0' {
      return false
   }
   value, _ := strconv.Atoi(s)
   if value > 255 {
      return false
   }
   return true
}

总结

Medium题目，题目同leetcode 93.复原IP地址