Halo

A magic place for coding

0%

LeetCode 解题报告(340) -- 17. Letter Combinations of a Phone Number

Problem

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.

Example

Example 1:

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

Example 2:

1
2
Input: digits = ""
Output: []

Example 3:

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

Constraints:

  • 0 <= digits.length <= 4
  • digits [i] is a digit in the range ['2', '9'].

Analysis

   题目给出一串数字,每个数字和字母的对应关系参考电话上的位置,要求把所有的组合都返回。因为每增加一个数字,都需要把改数字映射的字母都加上去,所以这个是很典型的 BFS 了。我们使用层数来判断是否终止,因为字符串的长度比定是等于数字的长度,所以迭代中带上层数作为参数;同时因为要组成字符串,所以当前拼接的字符串也是一个参数;然后还需要一个参数传入引用,用于存放结果。

   每次迭代时,首先判断是否满足终止条件。如果满足的话就把当前拼接的字符串放入到结果中;反之,则找到该数字对应的字符串,然后逐个字母添加进去,重新迭代。


Solution

   为了方便期间,可以把数字和字母的映射写成一个数组,方便迭代中访问。


Code

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
class Solution {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty ()) {
return {};
}
string dict [] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> result;
int size = digits.size ();

helper (digits, dict, 0, "", result);
return result;
}
private:
void helper(string digits, string dict [], int level, string out, vector<string>& result) {
if (level == digits.size ()) {
result.push_back (out);
return;
}
string str = dict [digits [level] - '2'];
for (int i = 0; i < str.size (); i++) {
helper (digits, dict, level + 1, out + str [i], result);
}
}
};

Summary

   这是一道字符串类型题目中很经典的 BFS 递归,这类题目的特点是需要找出字符串本身,所以在递归的参数中需要带上,然后要把终止条件带上,这里用了层数。这道题目的分享到这里,感谢你的支持!

Welcome to my other publishing channels