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

暴力枚举法

• 将字符串的分割视为"."的插入，由于要分割出四个数字，所以要插入三个"."。
• 分割的数字最多只有三个，所以第一个"."只能在前三个字符后面插入，后面的两个"."都在前一个"."的后三个字符后面插入。
• 分割的数字范围在[0, 255]范围内，每次分割完要判断分割后的每个数字是否符合范围，如果都符合范围的话就加入候选。
• 当分割的数字字符串只有一个字符时，这个字符必然是符合范围的数字，当分割的数字字符串超过一个字符时，要判断是否有先导"0"的存在，比如说"00","01"这种类型的数字，虽然转换为数字后范围在[0, 255]之间，但是会丢失原字符串的"0"，所以也是不符合规范的。
• 时间复杂度：三层循环每次循环四次，可以视为常数级时间复杂度为O(1)。
• 空间复杂度：需要一个长度为4的数组保存数字，跟字符串的长度无关，所以也是常数级O(1)。

/**
 *
 * @param s string字符串
 * @return string字符串一维数组
 */
function restoreIpAddresses(s) {
    // 将字符串的分割视为"."的插入
    const allConvertIP = [];
    const currentSplitNums = [];
    let convertIP;
    let isCorrectNums;

    for (let i = 1; i < s.length-2 && i < 4; ++i) {  // 第一个"."只能在前三个字符后插入，且最多插在后三个字符前面。
        for (let j = i+1; j < s.length-1 && j < i+4; ++j) {
            for (let k = j+1; k < s.length && k < j+4; ++k) {
                currentSplitNums.push(s.substring(0, i), s.substring(i, j), s.substring(j, k), s.substring(k));
                isCorrectNums = currentSplitNums.every((item => { return Number(item) <= 255 && (item.length === 1 || item[0] !== "0")}));
                if (isCorrectNums) {
                    convertIP = currentSplitNums.join(".");
                    allConvertIP.push(convertIP);
                }
                currentSplitNums.splice(0, currentSplitNums.length);
            }
        }
    }

    return allConvertIP;
}
module.exports = {
    restoreIpAddresses: restoreIpAddresses,
};

递归回溯法

• 要从左到右分析问题，每次递归从字符串左边取1到3个字符，作为第一个数字，然后将递归处理剩下的字符串。
• 每次递归要分析所得到的数字是否符合规范，符合规范则添加到临时存放数字的数组中，不符合规范的进行剪枝操作。
• 每次回溯要弹出上次递归最后进入临时数组中的数字，因为这个数组要用来重复更新数字。
• 递归退出条件为临时数组长度达到4且此时达到了字符串末尾，这时代表已经获分割了四个数字，且这四个数字是由整个字符串分割得到的，而不是某个子串分割的数字。并且还要判断当前处理的字符串是否达到末尾，因此需要一个记录每次递归处理的字符串开始索引的变量，每次递归传入这个变量，通过这个变量判断是否达到了字符串的末尾。

参考

https://blog.nowcoder.net/n/fbc99f393cfc477fb9c3e728c0417986?f=comment

/**
  * 
  * @param s string字符串 
  * @return string字符串一维数组
  */
function restoreIpAddresses( s ) {
    // write code here
    const allConvertIP = [];

    // 第一种递归方式，每次递归都处理同一个字符串，但需要一个索引指示从字符串的哪里开始处理
    function dfs(s, startIndex, currentSplitNums) {
        if (currentSplitNums.length === 4) {  // 此时已经收集好4个分割的数字
            if (startIndex === s.length) {  // 下标必须走到字符串末尾才收集，避免收集前面子串的转换IP
                const convertIP = currentSplitNums.join(".");
                allConvertIP.push(convertIP);
            }
            return;
        }

        let splitNumStr = "";
        let splitNum;
        for (let i = startIndex; i < startIndex+3 && i < s.length; ++i) {
            splitNumStr += s[i];
            splitNum = Number(splitNumStr);

            // 如何判断先导0的情况要注意，&&表示前面的满足情况后再if判断后面的条件，||表示前面的不满足情况后再判断后面的条件
            if (splitNum >= 0 && splitNum <= 255 && (splitNumStr.length === 1 || splitNumStr[0] !== "0")) {  // 剪枝部分
                currentSplitNums.push(splitNum);
                dfs(s, i+1, currentSplitNums);  // 当前分割的数字符合规范才继续递归
                // 回溯部分
                currentSplitNums.pop();
            }
        }
    }

    // 第二种递归方式，每次递归剩余的子串
    function dfs_b(s, currentSplitNums) {
        if (currentSplitNums.length === 4) {  // 此时已经收集好4个分割的数字
            if (s.length === 0) {  // 下标必须走到字符串末尾才收集，避免收集前面子串的转换IP
                const convertIP = currentSplitNums.join(".");
                allConvertIP.push(convertIP);
            }
            return;
        }

        let splitNumStr = "";
        let splitNum;
        for (let i = 0; i < 3 && i < s.length; ++i) {
            splitNumStr += s[i];
            splitNum = Number(splitNumStr);

            // 如何判断先导0的情况要注意，&&表示前面的满足情况后再if判断后面的条件，||表示前面的不满足情况后再判断后面的条件
            if (splitNum >= 0 && splitNum <= 255 && (splitNumStr.length === 1 || splitNumStr[0] !== "0")) {  // 剪枝部分
                currentSplitNums.push(splitNum);
                dfs(s.substring(i+1), currentSplitNums);  // 当前分割的数字符合规范才继续递归
                // 回溯部分
                currentSplitNums.pop();
            }
            
            
        }
    }

    dfs(s, 0, []);
    return allConvertIP;
}