电话号码的字母组合

题目要求

给定一个字符串，该字符串由数字 2 到 9 组成。要求编写一个算法，找出这个字符串所能代表的所有可能的字母组合。字母组合与电话按键上的字母对应，即：

• 2 对应 a, b, c
• 3 对应 d, e, f
• 4 对应 g, h, i
• 5 对应 j, k, l
• 6 对应 m, n, o
• 7 对应 p, q, r, s
• 8 对应 t, u, v
• 9 对应 w, x, y, z

注意：

• 输入字符串的长度不固定，但仅包含数字 2-9。
• 输出的字母组合可以是任意顺序。
• 数字 1 不对应任何字母，因此在输入字符串中不会出现。

解题思路

这个问题可以通过回溯算法来解决。回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个有效的解，回溯算法会丢弃它，并回溯到上一步然后尝试另一种可能。

对于这个问题，我们可以定义如下的回溯过程：

1. 从输入字符串的第一个数字开始。
2. 将当前数字对应到其能代表的所有字母。
3. 对于当前数字对应的每一个字母，将其加到目前为止的组合中，并对输入字符串的下一个数字进行相同的处理。
4. 当我们到达输入字符串的末尾时，我们将当前的字母组合加入到结果集中。
5. 如果还没有到达字符串末尾，继续对剩余的数字进行步骤 2 到 4 的处理。
6. 一旦处理完一个字母，回溯到前一个字母，移除当前字母，尝试下一个可能的字母组合。

通过这样的方式，我们可以确保探索了所有可能的字母组合，并且当我们到达字符串的末尾时，我们会有一个完整的组合加入到结果集中。这个过程会一直重复，直到所有的组合都被找到为止。

Golang 版本

package main

import "fmt"

func letterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }

    phoneMap := map[byte]string{
        '2': "abc", '3': "def", '4': "ghi", '5': "jkl",
        '6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz",
    }

    var combinations []string
    var backtrack func(index int, path []byte)
    backtrack = func(index int, path []byte) {
        if index == len(digits) {
            combinations = append(combinations, string(path))
            return
        }
        letters := phoneMap[digits[index]]
        for i := 0; i < len(letters); i++ {
            path = append(path, letters[i])
            backtrack(index+1, path)
            path = path[:len(path)-1]
        }
    }

    backtrack(0, []byte{})
    return combinations
}

func main() {
    digits := "23"
    fmt.Println(letterCombinations(digits))
}

这段代码定义了一个letterCombinations函数，它接受一个字符串digits作为输入，并返回一个字符串切片，包含了所有可能的字母组合。在main函数中，我们调用了letterCombinations函数，并打印出结果。这个实现使用了回溯算法，通过递归函数backtrack来生成所有可能的字母组合。

C++版本

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        unordered_map<char, string> phoneMap{
            {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
            {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
        };
        vector<string> combinations;
        string currentCombination;
        backtrack(combinations, phoneMap, digits, 0, currentCombination);
        return combinations;
    }

private:
    void backtrack(vector<string>& combinations, const unordered_map<char, string>& phoneMap,
                   const string& digits, int index, string& currentCombination) {
        if (index == digits.length()) {
            combinations.push_back(currentCombination);
            return;
        }
        const string& letters = phoneMap.at(digits[index]);
        for (const char& letter : letters) {
            currentCombination.push_back(letter);
            backtrack(combinations, phoneMap, digits, index + 1, currentCombination);
            currentCombination.pop_back();
        }
    }
};

int main() {
    Solution solution;
    string digits = "23";
    vector<string> combinations = solution.letterCombinations(digits);
    for (const string& combination : combinations) {
        cout << combination << endl;
    }
    return 0;
}

这段 C++代码实现了一个Solution类，其中包含了letterCombinations方法，用于计算并返回所有可能的字母组合。main函数中创建了一个Solution对象，并调用了letterCombinations方法，然后打印出所有的组合。这个实现同样使用了回溯算法，通过私有方法backtrack来递归地构建所有可能的组合。

Python 版本

from typing import List

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        phone_map = {
            '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
        }

        def backtrack(index: int, path: str):
            if index == len(digits):
                combinations.append(path)
                return
            for letter in phone_map[digits[index]]:
                backtrack(index + 1, path + letter)

        combinations = []
        backtrack(0, "")
        return combinations

# Example usage:
if __name__ == '__main__':
    solution = Solution()
    digits = "23"
    print(solution.letterCombinations(digits))

这段 Python 代码定义了一个Solution类，其中包含了letterCombinations方法，它接受一个字符串digits作为输入，并返回一个字符串列表，包含了所有可能的字母组合。在if __name__ == '__main__':块中，我们创建了一个Solution实例，并调用了letterCombinations方法，然后打印出结果。这个实现使用了回溯算法，通过嵌套的backtrack函数来递归地生成所有可能的字母组合。

Java 版本

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.HashMap;

public class Solution {
    private 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) {
        List<String> combinations = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return combinations;
        }
        backtrack(combinations, digits, 0, new StringBuilder());
        return combinations;
    }

    private void backtrack(List<String> combinations, String digits, int index, StringBuilder path) {
        if (index == digits.length()) {
            combinations.add(path.toString());
            return;
        }
        String possibleLetters = phoneMap.get(digits.charAt(index));
        for (char letter : possibleLetters.toCharArray()) {
            path.append(letter);
            backtrack(combinations, digits, index + 1, path);
            path.deleteCharAt(path.length() - 1);
        }
    }

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

这段 Java 代码定义了一个Solution类，其中包含了letterCombinations方法，它接受一个字符串digits作为输入，并返回一个字符串列表，包含了所有可能的字母组合。main方法中创建了一个Solution实例，并调用了letterCombinations方法，然后打印出所有的组合。这个实现使用了回溯算法，通过私有方法backtrack来递归地构建所有可能的组合。

Rust 版本

use std::collections::HashMap;

fn letter_combinations(digits: String) -> Vec<String> {
    let mut res = Vec::new();
    if digits.is_empty() {
        return res;
    }

    let phone_map: HashMap<char, &str> = [
        ('2', "abc"), ('3', "def"), ('4', "ghi"), ('5', "jkl"),
        ('6', "mno"), ('7', "pqrs"), ('8', "tuv"), ('9', "wxyz"),
    ].iter().cloned().collect();

    fn backtrack(
        res: &mut Vec<String>,
        phone_map: &HashMap<char, &str>,
        digits: &str,
        index: usize,
        combination: &mut String,
    ) {
        if index == digits.len() {
            res.push(combination.clone());
            return;
        }

        if let Some(letters) = phone_map.get(&digits.chars().nth(index).unwrap()) {
            for letter in letters.chars() {
                combination.push(letter);
                backtrack(res, phone_map, digits, index + 1, combination);
                combination.pop();
            }
        }
    }

    backtrack(&mut res, &phone_map, &digits, 0, &mut String::new());
    res
}

fn main() {
    let digits = "23".to_string();
    let combinations = letter_combinations(digits);
    for combination in combinations {
        println!("{}", combination);
    }
}

这段 Rust 代码定义了一个letter_combinations函数，它接受一个String类型的digits作为输入，并返回一个包含所有可能字母组合的Vec<String>。在main函数中，我们调用了letter_combinations函数，并遍历打印出所有的组合。这个实现使用了回溯算法，通过一个嵌套的backtrack函数来递归地生成所有可能的字母组合。

总结

上述解法在不同编程语言中实现了相同的功能：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。这个问题通常通过回溯算法来解决，因为需要探索所有可能的字母组合，直到找到所有的解。

在每种语言的实现中，都定义了一个映射（字典、哈希表等），将每个数字映射到对应的字母字符串。然后，使用回溯的方法，从第一个数字开始，对于每个可能的字母，都递归地进行探索，直到达到字符串的末尾。每当到达字符串的末尾时，就将当前的字母组合添加到结果集中。

不同语言之间的主要区别在于语法和一些特定的 API 调用。例如：

• 在 C++中，使用了std::vector和std::unordered_map来存储组合和映射。
• 在 Python 中，使用了列表和字典，并且有更简洁的循环和字符串处理方式。
• 在 Java 中，使用了ArrayList和HashMap，以及StringBuilder来高效地构建字符串。
• 在 Rust 中，使用了Vec和HashMap，以及 Rust 特有的所有权和借用规则来管理内存。

尽管实现的细节不同，但所有这些解法都遵循了相同的算法逻辑。