题意：

image.png

解题思路：

  1. 思路：
  2. 1. 长度不能大于12
  3. 2. 每次取s中的1-3位，递归下去，每一个节点下面再取1-3位；
  4. 3. 根据1-3位来判断是否是合理的ip段；
  5. 4. 因为3个点最多可以分成4段ip子段，所以三叉树最多4层，这也是递归的终止条件；

图示：

WeChat0b40d2e2debdc1560845b2b14bfe95f0.png

PHP代码实现：

  1. class Solution {
  3.     /**
  4.      * @param String $s
  5.      * @return String[]
  6.      */
  7.     public $res = [];
  8.     function restoreIpAddresses($s) {
  9.         if (strlen($s) > 12) return [];
  10.         $this->restore($s, 4, "");
  11.         return $this->res;
  12.     }
  14.     function restore($s, $k, $ipString) {
  15.         if ($k == 0 && strlen($s) == 0) {
  16.             //去掉最后一个.
  17.             $str = substr($ipString, 0, strlen($ipString) - 1);
  18.             array_push($this->res, $str);
  19.             return;
  20.         }
  21.         for ($i = 1; $i <= 3; $i++) {
  22.             if (strlen($s) < $i || !$this->valid(substr($s, 0, $i))) {
  23.                 continue;
  24.             }
  25.             $this->restore(substr($s, $i), $k - 1, $ipString. substr($s, 0, $i). '.');
  26.         }
  27.     }
  28.     function valid($s) {
  29.         if ($s == "" || (strlen($s) > 1 && $s[0] == "0")) return false;
  30.         return $s >= 0 && $s <= 255;
  31.     }
  32. }

GO代码实现：

  1. func restoreIpAddresses(s string) []string {
  2.    res := []string{}
  3.    if len(s) > 12 {
  4.        return nil
  5.    }
  6.    dfs(s, "", &res, 4)
  7.    return res 
  8. }
  9. func dfs(s string, tmp string, res *[]string, k int) { 
  10.     if k == 0 && len(s) == 0 {
  11.         *res = append(*res, tmp[:len(tmp)-1])
  12.     }
  13.     for i := 1; i <= 3; i++ { //分别取s中的1-3位
  14.         if len(s) < i { //超出3位长度
  15.             continue
  16.         }
  17.         str := s[:i]
  18.         if !valid(str) {
  19.             continue
  20.         }
  21.         dfs(s[i:], tmp+str+".", res, k - 1)
  22.     }
  23. }
  25. func valid(s string) bool {
  26.     if len(s) > 1 && s[0] == '0' {
  27.         return false
  28.     }
  29.     v, err := strconv.Atoi(s)
  30.     if err != nil {
  31.         return false
  32.     }
  33.     return v >= 0 && v <= 255
  34. }