93. Restore IP Addresses

Leetcode link

题目简介

/**
 * @param {string} s
 * @return {string[]}
 */

题目给我们一个字符串 s

要求我们列出 s 能组合成的所有 ip 地址

解题思路

列出 IP 地址本质就是在对的地方放 .，也就是说它其实是一种组合问题

这类问题我们可以用回溯来求解，但有两个地方需要注意：

1. 每一个组合最多只能有 3 个字符
2. 并不是所有的组合都可以是 IP 地址的一项

我们要在回溯中对上述两种情况进行排除

最后符合条件的组合放进数组中返回即可

Javascript

/**
 * @param {string} s
 * @return {string[]}
 */
var restoreIpAddresses = function (s) {
    const len = s.length
    const res = []

    const isValid = (segment) => {
        // rule out 0xx
        if (segment.length > 1 && segment[0] === '0') {
            return false
        }
        const num = parseInt(segment, 10)
        return num >= 0 && num <= 255
    }

    const backtrack = (start, arr) => {
        if (arr.length === 4) {
            if (start === len) {
                res.push(arr.join('.'))
            }
            return
        }

        for (let offset = 1; offset <= 3; offset++) {
            const end = start + offset
            if(end > len) {
                break;
            }
            const segment = s.slice(start, end)
            if(isValid(segment)) {
                arr.push(segment)
                backtrack(end, arr)
                arr.pop()
            }
        }
    }

    backtrack(0, [])
    return res
};

复杂度分析

时间

因为我们每次回溯都要遍历三次，总共要进行 4 次回溯，所以需要遍历 次

所以总的时间复杂度是：O(1)

空间

不算 res 数组：O(1)