93 复原IP地址

leetcode链接

有效 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 地址。 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

题解

这一题和分割回文串比较类似，就是从每一位开始。我们需要考虑的是 怎么剪枝以及怎么终止递归（递归的终止条件）

递归三部曲：

一，递归的参数定义：s，currentResults, index 二，递归的终止条件 我这里写的比较简单，递归终止是index === s.length，也就是每次分割。其实更优的方案是，当currentResults的length===3终止递归，因为ip地址是4段的，求出前3段后最后一段就是s 减去 前三段。 三，递归的单层逻辑

//假设我们的函数是splitIp，参数是s,currentResults, index
for(let i=index;i<s.length;i++) {
    const left = s.slice(index, i+1)
    if (isValidIP(left)) {
        splitIp(s, [...currentResults, left], i+1)
    }
}

这里剪枝就是判断是不是合法的ip地址。合法的ip地址是0-255，非0不能以0开头。

    var isValidIP = function(s) {
        if(s.length > 1 && s.startsWith('0')) {
            return false
        }
        //parse to int
        const currentNum = parseInt(s)
        if(s>=0 && s<=255) {
            return true
        }
        return false
    }

整体上的代码就是：

var restoreIpAddresses = function(s) {
    var result = []
    var isValid = function(s) {
        if(s.length > 1 && s.startsWith('0')) {
            return false
        }
        //parse to int
        const currentNum = parseInt(s)
        if(s>=0 && s<=255) {
            return true
        }
        return false
    }
    var splitString = function(s, currentResult, index) {
        if(index >= s.length) {
            
            if(currentResult.length === 4) {
                result.push([...currentResult])
            }
            return
        }
        for(let i=index;i<s.length;i++) {
            const left = s.slice(index, i+1)
            if(isValid(left)) {
                splitString(s, [...currentResult, left], i+1)
            }
        }
    }
    splitString(s, [], 0)

    //console.log('aaa', result)
    return result.map(one => one.join("."))
};

采用只取前三段就结束递归

var restoreIpAddresses = function(s) {
    var result = []
    var isValid = function(s) {
        if(s.length === 0) {
            return false
        }
        if(s.length > 1 && s.startsWith('0')) {
            return false
        }
        //parse to int
        const currentNum = parseInt(s)
        if(s>=0 && s<=255) {
            return true
        }
        return false
    }
    var splitString = function(s, currentResult, groupsCount, index) {
        //第三组就结束递归
        if(groupsCount === 3) {
            const right = s.slice(index, s.length)
            if(isValid(right)) {
                result.push(currentResult+'.'+right)
            }
            return
        }
        for(let i=index;i<s.length;i++) {
            const left = s.slice(index, i+1)
            if(isValid(left)) {
                splitString(s, index === 0 ? left : currentResult+'.'+left, groupsCount+1, i+1)
            }
        }
    }
    splitString(s, '', 0, 0)

    return result
};