输出一个字符串的多种变体

93. 复原 IP 地址

对一个字符串加入

/**
 * @param {string} s
 * @return {string[]}
 */
 var restoreIpAddresses = function(s) {
    let n = s.length;
    if (n <= 3) {
        return [];
    }
    let ans = [];
    function dfs(path, start) {
        if (path.length === 4) { // 结束条件要仔细看
            if (start === n) {
                ans.push(path.join('.'));
            }
            return;
        }
        for (let i = 1; i <= 3; i++) {
            let cur = s.slice(start, start + i); // slice(start, length) 这样去记录
            if (/^0/.test(cur) && cur.length > 1) {
                break;
            }
            cur = Number(cur);
            if (cur > 255) {
                break;
            }
            dfs([...path, cur], start + i);
        }
    }
    dfs([], 0); // 这类题目，dfs 的 path 是必传
    return ans;
};

很类似的题目，但是使用的是动态规划：

var numDecodings = function(s) { // 动态规划，没有要求具体的例子，只是要数目
    let n = s.length;
    if (n === 0) {
        return 0;
    }
    let dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    for (let i = 1; i < n + 1; i++) {
        if (s[i - 1] !== '0') {
            dp[i] = dp[i - 1];
        }
        let cur = s.slice(i - 2, i);
        if (Number(cur) <= 26 && (s[i - 2] !== '0') && i >= 2) {
            dp[i] += dp[i - 2]
        }
    }
    return dp[n];
};

也可以使用递归的手段，但是效率太低：

var numDecodings = function(s) {
    let n = s.length;
    let count = 0;
    function dfs(path, start) {
        let way = path.slice(path.lastIndexOf('.') + 1); // 注意寻找
        if (way[0] === '0') {
            return;
        } else if (way.length >= 3) {
            return;
        } else if (Number(way) > 26) {
            return;
        }
        if (start >= n) {
            count++;
            return;
        }
        dfs(path + '.' + s[start], start + 1);
        dfs(path + s[start], start + 1);
    }
    dfs('', 0)
    return count / 2;
};

131. 分割回文串

还是一样的套路。

var partition = function(s) {
    function isHuiWen(str) {
        return str === str.split('').reverse().join('');
    }
    let n = s.length;
    let ans = new Set();
    function dfs(path, start) {
        if (start >= n) {
            ans.add(path.join(','));
            return;
        }
        for (let i = 1; i <= n; i++) {
            let cur = s.slice(start, start + i);
            if (isHuiWen(cur)) {
                dfs([...path, cur], start + i);
            } else {
                continue;
            }
        }
    }
    dfs([], 0);
    return Array.from(ans).map(item => item.split(','));
};

但是时间很长。

jerray ai 的考题：

题目：给字符串 ‘123456789’，在其中添加‘+-’，使得

之和为100。

function dfs(path, start) {
    if (start === 10) {
        if (eval(path) === 100) {
            console.log(path);
        }
        return;
    }
    dfs(path + '+' + start, start + 1);
    dfs(path + '-' + start, start + 1);
    dfs(path + '' + start, start + 1);
}
dfs('', 1);