题解 | #数字字符串转化成IP地址#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param s string字符串 
 * @return string字符串一维数组
 */
function restoreIpAddresses( s ) {
    // write code here
    const results = [];
    
    // 回溯
    function backtrack(path, startIndex) {
        // 如果已经生成4个有效部分,且字符串已经遍历完,将结果添加到结果数组中
        if (path.length === 4 && startIndex === s.length) {
            results.push(path.join('.'));
            return;
        }
        // 如果已经生成了四个有效部分或者字符串已经遍历完,不再继续递归
        if (path.length === 4 || startIndex === s.length) {
            return;
        }
        // 尝试从1到3个数字作为IP地址的一部分
        for (let i=1; i<=3; i++) {
            if (startIndex + i > s.length) {
                break;
            }
            const part = s.substring(startIndex, startIndex + i);
            // 检查部分是否有效
            if (isValidPart(part)) {
                path.push(part); // 将有效部分添加到当前IP地址中
                backtrack(path, startIndex + i); // 递归生成下一部分
                path.pop(); // 回溯,移除组后一个部分
            }
        }
    }
    // isValidPart函数用于检查一个部分是否有效
    function isValidPart(part) {
        if (part.length === 0) {
            return false;
        }
        if (part.length > 1 && part[0] === '0') {
            return false; // 不能以0开头
        }
        const num = parseInt(part);
        return num >= 0 && num <= 255;
    }
    // 从字符串的起始位置开始回溯生成IP地址
    backtrack([], 0);
    // 返回所有可能的IP地址形式
     return results;
}
module.exports = {
    restoreIpAddresses : restoreIpAddresses
};

backtrack 函数

它递归生成所有可能的IP地址。

首先，它检查是否已经生成了4个有效部分并且字符串已经遍历完，如果是，就将当前IP地址加入结果数组。

然后，它检查是否已经生成了4个有效部分或者字符串已经遍历完，如果是，就返回，不再继续递归。

接下来，它使用一个循环来尝试从1到3个数字作为IP地址的一部分，并将部分添加到当前IP地址中。

isValidPart 函数

它调用 isValidPart 函数来检查这个部分是否有效。如果有效，就继续递归生成下一个部分，然后在回溯时移除最后一个部分，以便继续尝试其他可能的部分。

最后，我们从字符串的起始位置开始调用 backtrack 函数，开始生成所有可能的IP地址形式，并将它们存储在 results 数组中，最终返回这个数组。

这个算法的核心思想是通过回溯不断尝试不同的部分组合，直到找到所有可能的IP地址形式。