回溯
解题思路
以 25525511135 为例，第一步时有几种选择？
- 选 2 作为第一个片段；
- 选 25 作为第一个片段；
- 选 255 作为第一个片段；
能切三种不同的长度，切第二个片段时，又面临三种选择；
这会向下分支，形成一棵树，用 DFS 去遍历所有选择，必要时提前回溯；
因为某一步的选择可能是错的，得不到正确的结果，不要往下做了，撤销最后一个选择，回到选择前的状态，去试另一个选择；
图解
代码实现
var restoreIpAddresses = function (s) {
const res = [];
backtrack(res, s, 0, []);
return res;
};
const backtrack = (res, str, startInx, path) => {
if (path.length > 4) return;
// ip 地址 长度为 4 且 字符串全部用完了
if (path.length === 4 && startInx === str.length) {
res.push(path.join('.'));
return;
}
for (let i = startInx; i < str.length; i++) {
// 满足 ip 的条件
const num = str.substr(startInx, i - startInx + 1);
if (Number(num) > 255) break;
if (num.length > 1 && num[0] === '0') break;
path.push(num);
backtrack(res, str, i + 1, path);
path.pop();
}
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 131. 分割回文串
上一篇
评论
