算法 回溯(回溯算法总结)

图片授权基于 www.pixabay.com 相关协议

什么是回溯?
如果以迷宫的模式去理解就会好理解。
从迷宫入口开始,遇到分叉口,选择其中一条走下去,当这条路不通时,会退回到上个分叉口,重新换条路走,再不通,再换条路走,当前分叉口没有路了,返回父级的分叉口。
来,看道题…
题目:17. 电话号码的字母组合
难度:中等
链接:
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
内容:给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按「任意顺序」返回。
思考了一会,没啥好办法,第一次接触「回溯」。看了看题解,注意到只要有业务关键点在于「所有组合」那就会使用「回溯」。
关于题解,我是抄的。
    const letterCombinations = function (digits) {    const len = digits.length    if (digits === null || !len) return []    const phone = {        2: \\\'abc\\\',        3: \\\'def\\\',        4: \\\'ghi\\\',        5: \\\'jkl\\\',        6: \\\'mno\\\',        7: \\\'pqrs\\\',        8: \\\'tuv\\\',        9: \\\'wxyz\\\',    }    //存储最终结果    const res = [];    const mergeFn = (i, s) => {        if (i === len) {            res.push(s)            return        }        for (const dig of phone[digits[i]]) {            mergeFn(i + 1, s + dig)        }    }    mergeFn(0, \\\'\\\')    return res}

    参考资料:

    https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/dian-hua-hao-ma-de-zi-mu-zu-he-by-leetcode-solutio/

    https://leetcode.com/problems/letter-combinations-of-a-phone-number/discuss/139447/Clean-JavaScript-DFS-solution

    原创文章,作者:小道研究,如若转载,请注明出处:https://www.sudun.com/ask/34497.html

    (0)
    小道研究's avatar小道研究
    上一篇 2024年4月7日 下午9:58
    下一篇 2024年4月7日 下午10:00

    相关推荐

    发表回复

    您的邮箱地址不会被公开。 必填项已用 * 标注