«

Java电话号码的字母组合问题怎么解决

时间:2024-8-6 09:04     作者:韩俊     分类: 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"]

题解

    先把2-9对应的字符用一个map存起来

    我们可以知道这是一个全排列的问题

    每次我们找到一组满足条件的组合,只需把最后一个字符删除在找下一个,知道找完第一个字符对应的所有组合,回溯上一个字符往下,继续之前的操作

    因为不确定有几个确定字符,所以用递归的方式来确定for循环的次数

例如23

2=abc

3=def

Character c = digits.charAt(start);
String str = phoneMap.get(c);
for(int i = 0;i < str.length();i++){
    list1.add(str.charAt(i));
    help(digits,start+1);
    list1.remove(list1.size()-1);
}

先从map取出2对应的字符遍历,每次遍历会先把该字符存入一个list1容器,递归该方法会在嵌套一个for循环3对应字符长度,如果还有则继续嵌套,当lsit1容器大小与digits长度一样,说明找到了一组解,遍历存入集合结束该循环,代码在下方,因为要回溯,所以每次调用该方法后会把该list1长度减一,实现回溯的过程

class Solution {
    List<String> list = new ArrayList<>();
    List<Character> list1 = new ArrayList<>();
    Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
    public List<String> letterCombinations(String digits) {
        if(digits.length() == 0){
            return new ArrayList<>();
        }
        
        help(digits,0);
        return list;
    }
    public void help(String digits,int start){
        if(list1.size() == digits.length()){
            String str = "";
            for(int j = 0;j < list1.size();j++){
                str += list1.get(j);
            }
            list.add(str);
            return;
        }
        Character c = digits.charAt(start);
        String str = phoneMap.get(c);
        for(int i = 0;i < str.length();i++){
            list1.add(str.charAt(i));
            help(digits,start+1);
            list1.remove(list1.size()-1);
        }
    }
}

标签: java

热门推荐