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

题目描述

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']`

解题思路

``````#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

Built with Hugo
Theme Stack designed by Jimmy