【LeetCode:17. 电话号码的字母组合 | 递归 + 回溯 + 组合】

2023-12-30 18:41:33

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样?
🌲 作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯

🚀 算法题 🚀

在这里插入图片描述

在这里插入图片描述

🚩 题目链接

? 题目描述

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

示例 1:

输入:digits = “23”
输出:[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2:

输入:digits = “”
输出:[]
示例 3:

输入:digits = “2”
输出:[“a”,“b”,“c”]

提示:

0 <= digits.length <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

🌟 求解思路&实现代码&运行结果


? 递归 + 回溯 + 组合

🥦 求解思路
  1. 首先,我们先将题目给定的电话号码对应的字符重新进行收集,给出对应的映射关系,存储到char数组中,同时将digits进行进一步的转换,每个位置减2,和我们的char数组下标对应。
  2. 然后,通过我们的递归进行收集答案,和我们之前递归题目有一些改变的是,该题目的index控制的是digits每次选择的位置,循环选择的是对应位置下char字符,而我们之前的题目index控制的是现在选到了什么位置,然后基于此进行递归。说的更明白一些,该题目的index和每次选择字符位置是不同的数组,之前的递归是在相同的数组进行递归。这点要区分开。
  3. 实现代码如下所示:
🥦 实现代码
class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        char[][] arr = { { 'a', 'b', 'c' }, { 'd', 'e', 'f' }, { 'g', 'h', 'i' }, { 'j', 'k', 'l' }, { 'm', 'n', 'o' },
                { 'p', 'q', 'r', 's' }, { 't', 'u', 'v' }, { 'w', 'x', 'y', 'z' } };
        char[] c = digits.toCharArray();
        int n = c.length;
        if (digits == null || digits.length() == 0) {
            return ans;
        }
        int[] nums = new int[c.length];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = c[i] - '0' - 2;
        }
        char[] temp = new char[n];
        dfs(0, nums, ans, temp, arr, n);
        return ans;
    }

    public void dfs(int index, int[] nums, List<String> ans, char[] temp, char[][] arr, int n) {
        if (index == n) {
            ans.add(String.valueOf(temp));
            return;
        } 
        char[] c = arr[nums[index]]; 
        for (int j = 0; j < c.length; j++) {
            temp[index] = c[j];
            dfs(index + 1, nums, ans, temp, arr, n);
            temp[index] = ' ';
        }
    }
}
🥦 运行结果

在这里插入图片描述


💬 共勉

最后,我想和大家分享一句一直激励我的座右铭,希望可以与大家共勉!

在这里插入图片描述

在这里插入图片描述

文章来源:https://blog.csdn.net/Coder_ljw/article/details/135307207
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。