Skip to content

Latest commit

 

History

History
70 lines (52 loc) · 2.48 KB

93.md

File metadata and controls

70 lines (52 loc) · 2.48 KB

##Leetcode基础刷题之PHP解析(93. Restore IP Addresses)
. 2019-12-09 吴亲库里 库里的深夜食堂

✏️题目描述

给一组只含数字的字符串，返回所有有效的ip地址组合。。

✏️题目实例

​

✏️题目分析

ip地址的规则知道吧。ip地址分为四段，每一段的取值范围在0-255之间，第一段不能是0开头，其余的一位可以为0，但是不是一位的时候像00,01,001.....都是不合法的，我们在组合的时候还需要判断是否合法。相当于在分割字符串，判断每种情况是否合法。不合法的就跳过。用一个变量 k 表示四段 ip 地址，当 k=0 的时候并且当前字符串已经为空，说明四段已经分割完成，如果不等于0，对于每一段，我们都需要从1到3位去尝试。然后进行验证，至于验证，首先截取的数值肯定不能大于 255 ,其次，因为存在0开头的情况，所以我们先转化为整形，再对比一下长度即可。这是一道典型的有关回溯法的解，回溯法按照我的理解说白了，就是把所有的情况遍历一遍，它的解题方式可以使用递归，这是通常的解法，当然了能用递归一般都可以使用迭代。

✏️代码实现

/**
 * @param String $s
 * @return String[]
 */
function restoreIpAddresses($s)
{
    $res = [];
    $this->helper($s, 0, '', $res);
    return $res;
}

function helper($s, $n, $out, &$res)
{
    if ($n == 4) {
        if ($s == '') {
            array_push($res, $out);
        }
    } else {
        for ($k = 1; $k < 4; $k++) {
            if (strlen($s) < $k) {
                break;
            }
            $val = intval(substr($s, 0, $k));
            if ($val > 255 || $k != strlen($val)) continue;
            $this->helper(substr($s, $k), $n + 1, $out . substr($s, 0, $k) . ($n == 3 ? '' : '.'), $res);
        }
    }
}

这里在处理上的一个小技巧就是

$out . substr($s, 0, $k) . ($n == 3 ? '' : '.')

很好理解，因为最后一段最后面不需要用点来分割。

联系

​