93. 复原IP地址

题意：

解题思路：

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

图示：

PHP代码实现：

class Solution {
    /**
     * @param String $s
     * @return String[]
     */
    public $res = [];
    function restoreIpAddresses($s) {
        if (strlen($s) > 12) return [];
        $this->restore($s, 4, "");
        return $this->res;
    }
    function restore($s, $k, $ipString) {
        if ($k == 0 && strlen($s) == 0) {
            //去掉最后一个.
            $str = substr($ipString, 0, strlen($ipString) - 1);
            array_push($this->res, $str);
            return;
        }
        for ($i = 1; $i <= 3; $i++) {
            if (strlen($s) < $i || !$this->valid(substr($s, 0, $i))) {
                continue;
            }
            $this->restore(substr($s, $i), $k - 1, $ipString. substr($s, 0, $i). '.');
        }
    }
    function valid($s) {
        if ($s == "" || (strlen($s) > 1 && $s[0] == "0")) return false;
        return $s >= 0 && $s <= 255;
    }
}

GO代码实现：

func restoreIpAddresses(s string) []string {
   res := []string{}
   if len(s) > 12 {
       return nil
   }
   dfs(s, "", &res, 4)
   return res 
}
func dfs(s string, tmp string, res *[]string, k int) { 
    if k == 0 && len(s) == 0 {
        *res = append(*res, tmp[:len(tmp)-1])
    }
    for i := 1; i <= 3; i++ { //分别取s中的1-3位
        if len(s) < i { //超出3位长度
            continue
        }
        str := s[:i]
        if !valid(str) {
            continue
        }
        dfs(s[i:], tmp+str+".", res, k - 1)
    }
}
func valid(s string) bool {
    if len(s) > 1 && s[0] == '0' {
        return false
    }
    v, err := strconv.Atoi(s)
    if err != nil {
        return false
    }
    return v >= 0 && v <= 255
}