0%

[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,接下来用回溯法进行暴力遍历选出所有的字母组合即可,每一次循环遍历当前数字的所有字母。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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