【LeetCode Hot 100】17. 电话号码的字母组合

louistang0524 / 2024-09-25 / 原文

题目描述

本题需要用回溯算法遍历穷举所有可能的解。回溯算法维护一个字符串序列，记录已经有的字母排列，用一个索引值记录该字符串序列下一个将要处理的位置。每次递归将索引值加一，回溯之后将字符串序列中上次加入的字符退出序列中，枚举下一个可能的值。总的来说是一个较为基础的回溯算法题目，我们可以用这个题目来理解回溯算法的基础知识。

// C++
class Solution {
public:
    unordered_map<char, string> digit2letters = {
        {'2', "abc"}, {'3', "def"},  {'4', "ghi"}, {'5', "jkl"},
        {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};

    vector<string> result;

    void backtrace(string& digits, int idx, string& combination) {
        if (idx >= digits.length()) {
            result.push_back(combination);
            return;
        }

        string& possible = digit2letters[digits[idx]];
        for (char c : possible) {
            combination.push_back(c);
            backtrace(digits, idx + 1, combination);
            combination.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        if (digits.length() == 0) {
            return {};
        }

        string combination = "";
        backtrace(digits, 0, combination);
        return result;
    }
};

// Java
class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits.length() == 0) {
            return res;
        }

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

        StringBuffer combination = new StringBuffer();
        backtrace(res, map, digits, 0, combination);
        return res;
    }

    public void backtrace(List<String> res, Map<Character, String> map, String digits, int idx, StringBuffer combination) {
        if (idx >= digits.length()) {
            res.add(combination.toString());
            return;
        }

        String letters = map.get(digits.charAt(idx));
        for (int i = 0; i < letters.length(); i++) {
            combination.append(letters.charAt(i));
            backtrace(res, map, digits, idx + 1, combination);
            combination.deleteCharAt(idx);
        }
    }
}

对于个人来说，Java解法的重点在于Java标准库的使用，比如Map以及用于构建字符串的StringBuffer。