题目描述

给定一个仅包含数字 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"]

PHP 示例代码

function letterCombinations($digits) {
    if (empty($digits)) return [];

    $map = [
        '2' => 'abc',
        '3' => 'def',
        '4' => 'ghi',
        '5' => 'jkl',
        '6' => 'mno',
        '7' => 'pqrs',
        '8' => 'tuv',
        '9' => 'wxyz'
    ];

    $result = [];
    backtrack($digits, $map, '', $result);
    return $result;
}

function backtrack($digits, $map, $current, &$result) {
    if (empty($digits)) {
        $result[] = $current;
        return;
    }

    $digit = $digits[0];
    $letters = $map[$digit];
    for ($i = 0; $i < strlen($letters); $i++) {
        backtrack(substr($digits, 1), $map, $current . $letters[$i], $result);
    }
}

// 示例用法
$digits = "23";
$combinations = letterCombinations($digits);
print_r($combinations);

Python 示例代码

def letterCombinations(digits):
    if not digits:
        return []

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

    def backtrack(index, current):
        if index == len(digits):
            result.append(current)
            return

        letters = mapping[digits[index]]
        for letter in letters:
            backtrack(index + 1, current + letter)

    result = []
    backtrack(0, '')
    return result

# 示例用法
digits = "23"
combinations = letterCombinations(digits)
print(combinations)

JavaScript 示例代码

function letterCombinations(digits) {
    if (!digits) return [];

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

    const result = [];

    function backtrack(index, current) {
        if (index === digits.length) {
            result.push(current);
            return;
        }

        const letters = map[digits[index]];
        for (let letter of letters) {
            backtrack(index + 1, current + letter);
        }
    }

    backtrack(0, '');
    return result;
}

// 示例用法
const digits = "23";
const combinations = letterCombinations(digits);
console.log(combinations);

在以上示例中，我们使用了回溯算法来生成所有可能的字母组合。每个数字对应的字母集合被逐一添加到当前组合的末尾，并递归地处理剩余的数字。通过这种方式，我们可以得到所有可能的组合。