依旧按照代码随想录的顺序刷题。进入分割专题。简介套路和 131. 分割回文串 一致但是在细节方面的处理比较繁琐。判断子串是否为有效 ip一开始需要判断截取的子串是否符合有效 ip较容易直接贴上代码。/** * param {string} s * param {string} start * param {string} end * return {boolean} */ // 左闭右闭 const isIpAddress (s, start, end) { // 根据区间 [start, end 1)左闭右开截取子字符串 const str s.slice(start, end 1); // 当子字符串首位是 0且不是个位数则一定不是合法的 ip 地址 // 如 01、011 等 if (str.length 1 str[0] 0) { return false; } const ipNum Number(str); // 过滤掉在 [0, 255] 区间外的 ip 地址 if (ipNum 0 || ipNum 255) { return false; } return true; };截取子串方面则是根据开始索引 startIndex 以及结束索引 i 选取。for (let i startIndex; i s.length; i) { if (isIpAddress(s, startIndex, i)) { // 根据区间 [startIndex, i 1)左闭右开截取子串 const ipAddress s.slice(startIndex, i 1); // 处理元素 } else { continue; } backtracking(); // 递归伪代码 // 回溯操作 }难点难点在于将截取的合法子串转换为规定的 ip 地址。一开始通过定义全局字符串变量 ipPath然后在单层递归逻辑中加上截取的子串以及符号.。但是这种方法很繁琐。因为在回溯的时候不仅要考虑符号 .还要考虑每一次加入的截取子串的长度来做删减。且还要单独处理 ip 地址末尾的数字后不需要加符号 . 的情况。导致顺着这种逻辑定义越来越多的变量代码越写越乱也不能很好地处理终止条件。解决方法后来采用定义全局数组变量 ipPath 的方式也就是前几次组合专题的套路。const ipPath []; // 一维数组 const result []; // 二维数组在单层递归逻辑中只需要在递归函数执行前把截取的子串转换为数字加入数组末尾在回溯的时候弹出数组末尾元素即可。for (let i startIndex; i s.length; i) { if (isIpAddress(s, startIndex, i)) { const ipAddress s.slice(startIndex, i 1); ipPath.push(Number(ipAddress)); // 加入数组末尾 } else { continue; } backtracking(s, i 1); ipPath.pop(); // 做相应回溯操作 }最后在终止条件中通过容器内置方法 Array.prototype.join()将数组 ipPath 转换为以 . 为分隔符的字符串后加入到二维数组 result 中。// 将 ip 数组转换为以 . 分隔的 ip 地址 result.push(ipPath.join(.));// Array.prototype.join() 用法示例 const arr [1, 2, 3, 4]; arr.join( | ); // 1 | 2 | 3 | 4 // 不提供参数则默认用逗号分隔 arr.join(); // 1, 2, 3, 4从而无需在递归函数中定义各种变量来辅助转换字符串过程更为简便。剪枝操作在终止条件方面和代码随想录常规题解不同博主想了一个隐含的剪枝操作。一开始的终止条件是通过判断开始索引 startIndex 大于等于字符串 s 长度后比较全局数组变量 ipPath 的长度是否为 4ip 地址的个数。if (startIndex s.length) { if (ipPath.length 4) { result.push(ipPath.join(.)); return; } }但是这种方法需要遍历一整个字符串而有的字符串在切割前 4 个子串的时候剩余待切割的子串很明显是不符合有效 ip 的没有必要继续遍历。拿字符串 s 25525511135 举例切割的符合合法 ip 的子串可以是2、5、5、2、……那么除了已经切割的前 4 个子串剩余子串为 5511135很明显该子串不符合合法 ip。因此剪枝的方法在于对切割的前 4 个子串做拼接。// 当收集到的路径ip 数组长度为 4 if (ipPath.length 4) { let ipAddresses ; // 将数组中的每一个 ip 字符串拼接 for (const ip of ipPath) { ipAddresses ip; } // …… }若拼接后的字符串和原字符串 s 一致说明变量 ipPath 收集的元素均是有效 ip且每个子串拼接可以覆盖到完整的原字符串 s。// 当收集到的路径ip 数组长度为 4 if (ipPath.length 4) { let ipAddresses ; // 将数组中的每一个 ip 字符串拼接 for (const ip of ipPath) { ipAddresses ip; } // 若拼接后和原字符串一致说明是一个合法的 ip 数组 if (ipAddresses s) { // 将 ip 数组转换为以 . 分隔的 ip 地址 result.push(ipPath.join(.)); return; } }否则在切割前 4 个子串后一定存在剩余待切割的子串此时该子串一定不符合有效 ip。参考代码/** * param {string} s * param {string} start * param {string} end * return {boolean} */ // 判断是否是合法的 ip 地址区间左闭右闭 const isIpAddress (s, start, end) { const str s.slice(start, end 1); if (str.length 1 str[0] 0) { return false; } const ipNum Number(str); if (ipNum 0 || ipNum 255) { return false; } return true; }; /** * param {string} s * return {string[]} */ var restoreIpAddresses function(s) { const [ipPath, result] [[], []]; // 数组的解构赋值 // 等价于 // const ipPath []; // const result []; /** * param {string} s * param {number} startIndex * return {void} */ const backtracking (s, startIndex) { // 当收集到的路径ip 数组长度为4 if (ipPath.length 4) { let ipAddresses ; // 将数组中的每一个 ip 字符串拼接 for (const ip of ipPath) { ipAddresses ip; } // 若拼接后和原字符串一致说明是一个合法的 ip 数组 if (ipAddresses s) { // 将 ip 数组转换为以 . 分隔的 ip 地址 result.push(ipPath.join(.)); return; } } for (let i startIndex; i s.length; i) { if (isIpAddress(s, startIndex, i)) { const ipAddress s.slice(startIndex, i 1); ipPath.push(Number(ipAddress)); } else { continue; } backtracking(s, i 1); ipPath.pop(); } }; backtracking(s, 0); return result; };