电话号码的字母组合

1.题目：

给定一个仅包含数字2-9的字符串，返回它能表示的所有可能的字母组合。数字到字母的映射如下（与电话按键相同）

输入格式：

2 -> abc
3 -> def
4 -> ghi
5 -> jkl
6 -> mno
7 -> pqrs
8 -> tuv
9 -> wxyz

输出格式：

一个字符串，仅包含数字2-9。

输入样例:

"23"

输出样例：

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

2.分析:

这个问题可以通过回溯法来解决。我们可以定义一个递归函数，该函数尝试为当前数字选择一个字母，并递归地为下一个数字选择字母，直到构建出完整的组合。

解析：

状态定义：

path：当前构建的字母组合。 output：存储所有可能的字母组合的列表。

状态转移方程：

对于输入字符串中的每个数字，找到所有对应的字母，并递归地为每个字母调用递归函数，同时将当前字母添加到path中。

初始条件和边界：

当path的长度等于输入字符串的长度时，将path添加到output中。

算法的步骤：

初始化一个映射表，将数字映射到对应的字母。 初始化path和output。 从第一个数字开始，递归地构建所有可能的字母组合。 在递归的每一步中，为当前数字选择一个字母，并将其添加到path中。 如果path的长度等于输入字符串的长度，将path添加到output中。 回溯并尝试下一个字母。

3.代码

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

public class Solution {
    // 电话按键对应的字符
    private static final String[] phoneMap = {
            "",     // 0
            "",     // 1
            "abc",  // 2
            "def",  // 3
            "ghi",  // 4
            "jkl",  // 5
            "mno",  // 6
            "pqrs", // 7
            "tuv",  // 8
            "wxyz"  // 9
    };

    public List<String> letterCombinations(String digits) {
        List<String> output = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return output;
        }

        backtrack(output, "", digits, 0);
        return output;
    }

    private void backtrack(List<String> output, String path, String digits, int index) {
        // 如果path的长度和digits的长度相等，说明找到了一个有效的组合
        if (index == digits.length()) {
            output.add(path);
            return;
        }

        // 获取当前数字对应的所有字符
        String digit = digits.substring(index, index + 1);
        String letters = phoneMap[Integer.parseInt(digit)];

        // 遍历所有字符，并递归
        for (int i = 0; i < letters.length(); i++) {
            backtrack(output, path + letters.charAt(i), digits, index + 1);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String digits = "23";
        List<String> combinations = solution.letterCombinations(digits);
        System.out.println("Combinations for " + digits + ":");
        for (String combination : combinations) {
            System.out.println(combination);
        }
    }
}

4.总结

本文档介绍了如何使用回溯法解决电话号码的字母组合问题。回溯法是一种深度优先搜索算法，它通过探索所有可能的候选解来寻找所有解。在这个问题中，我们构建了一个解空间树，每个节点代表一个数字对应的所有可能字母，通过递归遍历这棵树，我们可以找到所有可能的字母组合。

算法应用：

回溯法适用于解决组合问题、排列问题、划分问题等需要穷举所有可能解的问题。在电话号码的字母组合问题中，我们利用回溯法探索了所有可能的数字到字母的映射组合，直到找到所有符合条件的解。

复杂度介绍：

时间复杂度：

最坏情况下，我们需要探索所有可能的字母组合，对于每个数字，我们有3到4个可能的字母映射，因此时间复杂度为O(4^n)，其中n是输入字符串的长度。这意味着时间复杂度随着输入字符串长度的增加而指数增长。

空间复杂度：

空间复杂度主要取决于递归栈的深度和存储所有可能解的空间。在最坏情况下，空间复杂度为O(n)，其中n是输入字符串的长度，因为递归栈最多需要存储n个节点，同时我们还需要存储所有可能的解。

算法优势：

回溯法的优势在于其实现简单直观，对于许多组合问题，它提供了一种直接的解决方案。此外，它能够找到所有可能的解，而不仅仅是一个解，这在某些问题中是非常有用的。

算法局限：

回溯法也有其局限性。最明显的是它可能非常耗时，特别是对于大规模的问题，因为可能的解的数量可能非常大。此外，如果没有有效的剪枝策略，回溯法可能会做很多无用的工作。