Skip to content

17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

img

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Constraints:

  • 0 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9'].

Solution:

回溯三问:

  1. 当前操作? 枚举path[i] 要填入的字母
  2. 子问题? 构造字符串 >= i的部分
  3. 下一个子问题? 构造字符串 >= i + 1的部分

dfs(i) -> dfs(i + 1)

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<>();

        if (digits.length() == 0){
            return combinations;
        }

        Map<Character, String> letters = Map.of(
            '2', "abc", 
            '3', "def", 
            '4', "ghi", 
            '5', "jkl", 
            '6', "mno", 
            '7', "pqrs", 
            '8', "tuv", 
            '9', "wxyz"
        );

        backtrack(0, new StringBuilder(), digits, letters, combinations);
        return combinations;
    }

    private void backtrack(int index, StringBuilder sb, String digits, Map<Character, String> letters, List<String> combinations){
        if (sb.length() == digits.length()){
            combinations.add(sb.toString());
            return;
        }

        String possibleLetters = letters.get(digits.charAt(index));
        for (char letter : possibleLetters.toCharArray()){
            sb.append(letter);
            backtrack(index + 1, sb, digits, letters, combinations);

            sb.deleteCharAt(sb.length() - 1);
        }

    }
}

// TC: O(branch^level) = O(k^n) = O(4^n)
// SC: O(level) = O(n)

DFS vs Backtrack

区别分析：

  1. Terminology（术语上的区别）： - 上面的代码看似是 Backtracking 实现，实际上在某种程度上也可以被称为 DFS。这两者的差别更多在于问题类型和如何优化搜索，而不是在具体的实现细节上。 - DFS 更偏向于一种遍历方式，而 Backtracking 通常用于特定类型的问题，如组合问题、排列问题，且它会在无效的路径上做剪枝（通过回溯避免无效的搜索）。
  2. 搜索方式： - DFS 是沿着一条路径走到底再回溯，一般不做复杂的判断（只是在目标找到时结束）。 - Backtracking 则会在某些路径不符合条件时提前结束搜索（比如数独、N皇后问题中发现某个选择导致解无效，就会提前回溯）。

代码上的区别：

  • DFS 版本通常不强调剪枝机制，更多的是简单地递归遍历所有可能的路径。
  • Backtracking 版本则会在递归的过程中进行选择，并且通常带有“撤销选择”（即回溯）的机制。

综上，DFS 和 Backtracking 在实现上的区别其实并不大，都是通过递归进行深度搜索。在具体问题中，Backtracking 更强调“尝试 + 回溯”的过程，而 DFS 只是单纯地进行深度遍历。