分割回文串
js
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
js
/**
* @param {string} s
* @return {string[][]}
*/
var partition = function (s) {
let result = [];
function backtrack(track, i) {
if (i >= s.length) {
result.push([...track]);
return;
}
for (let j = i; j < s.length; j++) {
if (!isHuiWen(s.slice(i, j + 1))) continue;
// 判断是否回文
track.push(s.slice(i, j + 1));
backtrack(track, j + 1);
track.pop();
}
}
function isHuiWen(s) {
let tmp = s.split('');
while (tmp.length > 1) {
if (tmp.pop() !== tmp.shift()) return false;
}
return true;
}
backtrack([], 0);
return result;
};
复原 IP 地址
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
js
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
输入：s = "0000"
输出：["0.0.0.0"]
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
js
/**
* @param {string} s
* @return {string[]}
*/
var restoreIpAddresses = function (s) {
let result = [];
let path = [];
function backtracking(i) {
const len = path.length;
if (len > 4) return;
if (len === 4 && i === s.length) {
result.push(path.join('.'));
return;
}
for (let j = i; j < s.length; j++) {
let str = s.slice(i, j + 1);
if (str.length > 3 || Number(str) > 255) break;
if (str.length > 1 && str[0] === '0') break; // 如果当前字符超过1位，但是前导位是0 则跳过
path.push(str);
backtracking(j + 1);
path.pop();
}
}
backtracking(0);
return result;
};