题目: 电话号码的字母组合

来自智得网
跳转至： 导航、​ 搜索

分析

组合问题可以将所有组合枚举出来，也就是穷举法或者暴力破解法。

暴力破解

暴力破解将所有的数字转换为该数字可以表示的字母集合，然后依次从这些字母的集合中选出一位进行组合，将所有可能的组合值进行输出。

暴力破解的时间复杂度是Θ（3n）的时间复杂度。

暴力破解的空间复杂度也是Θ（n2）。

递归法

组合问题的特点是可以分为更小的子问题求解，最后将子问题的解进行合并。

该类组合问题可以用递归的方式求解，求解长度为n的数字的映射，可以先把长度为(n-1)数字的映射求解出来，之后把这个解空间中的每一项和最后一位数字可能表示的字母进行组合。

递归的过程依次减少长度，直到长度为1。

递归法的时间复杂度也是Θ（3n）。

回溯法

回溯法其实是针对递归法的一种优化，递归会存在调用栈较深的问题，回溯法使用深度遍历的方式求解问题，找到一个解之后，回溯到上一步骤寻找下一个解，直达把所有路径遍历完整。

递归法是一种常用的算法实现，递归的过程中是将问题划分为规模更小的子问题，同时将子问题的解作为当前解的一部分，例如本题中规模更小即长度更短的组合是当前解的前缀部分。

回溯法是一种算法思想，是穷举法的一种实现方式。

回溯过程中也有分步，但是这些步骤都没有形成解，只是解的一个步骤，例如在本题中回溯的时候之前的过程只是回溯的一个过程，之前的过程并没有形成单独的解。

穷举的过程中通过类似树结构的优化，减少穷举过程中的回退步骤，而对性能有一定的提升。

回溯法过程中树的深度是n，树的宽度是n*3，所以整体的时间复杂度也是Θ（3n）

回溯法使用的存储结构类似树的存储结构，空间复杂度也是Θ（n2）。 

因为该题的答案就是n个3元组的组合，所以从数学上组合方式就是3n，所以无论采用何种方式进行实现，时间复杂度都不可能低于3n。虽然不能整体降低时间复杂度的量集，但是通过回溯等确可以有效减少组合过程中的回退。
空间复杂度可以随着辅助数据结构的不同而有不同的时间复杂度。

解题

递归法

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class RecursionSolution {
    public static String[] NUM_MAPPING_ARRAY = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> solute(String digits){
        if(digits.length() == 1){
            return getChars(digits.charAt(0));
        }else{
            List<String> lastResult = solute(digits.substring(0, digits.length() - 1));
            List<String> currentChars = getChars(digits.charAt(digits.length() - 1));

            List<String> result = new ArrayList<>();
            for(String items : lastResult){
                for(String charString : currentChars){
                    result.add(String.join("", items, charString));
                }
            }

            return result;
        }
    }

    public List<String> getChars(char digitChar){
        String numMapping = NUM_MAPPING_ARRAY[digitChar - '0'];
        return numMapping.chars().mapToObj(c -> String.valueOf((char)c)).collect(Collectors.toList());
    }

    public static void main(String[] args){
        RecursionSolution solution = new RecursionSolution();
        List<String> result = solution.solute("23563");

        result.forEach(item->
                System.out.println(item)
        );
    }

}

回溯法

代码如下：

import java.util.ArrayList;
import java.util.List;

public class TracebackSolution {

    //初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""
    public static String[] NUM_MAPPING_ARRAY = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    //设置全局列表存储最后的结果
    List<String> list = new ArrayList<>();

    public List<String> solute(String digits) {
        if (digits == null || digits.length() == 0) {
            return list;
        }
        //迭代处理
        backTracking(digits, 0);
        return list;

    }

    //每次迭代获取一个字符串，所以会设计大量的字符串拼接，所以这里选择更为高效的 StringBuild
    StringBuilder temp = new StringBuilder();

    //比如digits如果为"23",num 为0，则str表示2对应的 abc
    public void backTracking(String digits, int num) {
        //遍历全部一次记录一次得到的字符串
        if (num == digits.length()) {
            list.add(temp.toString());
            return;
        }
        //str 表示当前num对应的字符串
        String str = NUM_MAPPING_ARRAY[digits.charAt(num) - '0'];
        for (int i = 0; i < str.length(); i++) {
            temp.append(str.charAt(i));
            //c
            backTracking(digits, num + 1);
            //剔除末尾的继续尝试
            temp.deleteCharAt(temp.length() - 1);
        }
    }

    public static void main(String[] args){
        TracebackSolution solution = new TracebackSolution();
        List<String> result = solution.solute("23563");

        result.forEach(item->
            System.out.println(item)
        );
    }

}
取自“https://www.aigetting.com/index.php?title=题目:电话号码的字母组合&oldid=2090”