LeetCode 93 还原IP地址

1 题目描述

给定一个仅包含数字的字符串,通过返回所有有效的IP地址组合来还原它。

例子:

输入:“25525511135”

输出:[“255.255.11.135”, “255.255.111.35”]

题目出处:

https://leetcode.com/problems/restore-ip-addresses/

2 解决思路

采用递归算法,require标识所需的数字段。

a)从最左分别取1-3个满足0~255的数字;

b)递归处理剩余字符串,且所需的数字段变为require-1;

c)若require为1,判断是否满足ip段内数字要求,满足返回,不满足返回空数组;

d)将a、b两步所得结果拼接为数组返回。

3 golang实现代码

https://github.com/olzhy/leetcode/blob/master/93_Restore_IP_Addresses/test.go

func restoreIpAddresses(s string) []string {
    return restore(s, 4)
}

func restore(s string, require int) []string {
    if 1 == require {
        if len(s) > 1 && '0' == s[0] {
            return []string{}
        }
        if v, _ := strconv.Atoi(s); v < 256 {
            return []string{s}
        }
        return []string{}
    }

    var r []string
    for i := 1; i < 4 && i+require-1 <= len(s); i++ {
        prefix := s[:i]
        if v, _ := strconv.Atoi(prefix); v < 256 {
            for _, j := range restore(s[i:], require-1) {
                r = append(r, prefix+"."+j)
            }
        }
        if '0' == s[0] {
            break
        }
    }
    return r
}