[Leetcode]17. Letter Combinations of a Phone Number(C++)

题目描述

题目链接：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 digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

例子

例子 1

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

例子 2

Input: digits = "" Output: []

例子 3

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

Constraints

0 <= digits.length <= 4

digits[i] is a digit in the range ['2', '9']

解题思路

使用一个哈希表创建数字到字母间的map，接下来用回溯法进行暴力遍历选出所有的字母组合即可，每一次循环遍历当前数字的所有字母。代码如下：

#include <string>
#include <vector>

class Solution {
public:
    std::vector<std::string> letterCombinations(std::string digits) {
        if (digits.empty()) return {};
        std::vector<std::string> nums{"",    "abc",  "def", "ghi", "jkl",
                                      "mno", "pqrs", "tuv", "wxyz"};
        std::string combination;
        std::vector<std::string> result;
        iterate(nums, 0, digits, combination, result);
        return result;
    }

private:
    void iterate(const std::vector<std::string>& nums, int idx,
                 const std::string& digits, std::string& combination,
                 std::vector<std::string>& result) {
        if (idx == digits.length()) {
            result.push_back(combination);
            return;
        }

        int digit = digits[idx] - '0' - 1;
        for (int i = 0; i < nums[digit].length(); i++) {
            combination.push_back(nums[digit][i]);
            iterate(nums, idx + 1, digits, combination, result);
            combination.pop_back();
        }
    }
};

时间复杂度: O((3~4)^n) 3 和 4 是每个数字可能对应的字母数字，n 为 digits 长度
空间复杂度: O((3~4)^n)

GitHub 代码同步地址： 17.LetterCombinationsOfAPhoneNumber.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions