1. 概述

给定一个只包含数字的字符串，复原它并返回所有可能的 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 = “101023”

输出：[“1.0.10.23”,”1.0.102.3”,”10.1.0.23”,”10.10.2.3”,”101.0.2.3”]

提示：

0 <= s.length <= 3000

s 仅由数字组成

2. 解题

<?php
class Solution
{
    private $res = [];
    /**
     * @param String $s
     * @return String[]
     */
    public function restoreIpAddresses($s)
    {
        if (strlen($s) > 12 || strlen($s) < 4) return $this->res;
        $this->do($s);
        return $this->res;
    }
    public function do($left, $separateNeed = 4, $ipStr = '')
    {
        if ($separateNeed == 0) {
            echo $ipStr . "\n";
            if (strlen($left) != 0) {
                return;
            }
            if(!filter_var($ipStr, FILTER_VALIDATE_IP, FILTER_FLAG_IPV4)) {
                return;
            }
            array_push($this->res, $ipStr);
            return;
        }
        for ($i = 1; $i <= 3; $i++) {
            $cut = substr($left, 0, $i);
            if (strlen($cut) < $i) {
                continue;
            }
            $ipSegment = ($separateNeed == 4) ? $cut : '.' . $cut;
            $ipStr .= $ipSegment;
            $left = substr($left, $i);
            $separateNeed = $separateNeed - 1;
            $this->do($left, $separateNeed, $ipStr);
            $ipStr = substr($ipStr, 0, strlen($ipStr) - strlen($ipSegment));
            $left = $cut . $left;
            $separateNeed = $separateNeed + 1;
        }
        return;
    }
}
// $s = '25525511135';
$s = '010010';
$cls = new Solution();
$ret = $cls->restoreIpAddresses($s);
print_r($ret);