Letter Combinations of a Phone Number

Posted by Bill on March 21, 2023

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

1
2
3
4
5
6
7
8
9
10
11
12
Example 1:

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

Input: digits = ""
Output: []
Example 3:

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

C++ Solution

一开始用的是Recursive的方法,直接LeetCode给我报Stack Overflow了,改为使用迭代的方式:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
 string numberToLetter(int num) {
  switch (num) {
    case 2:
      return "abc";
    case 3:
      return "def";
    case 4:
      return "ghi";
    case 5:
      return "jkl";
    case 6:
      return "mno";
    case 7:
      return "pqrs";
    case 8:
      return "tuv";
    case 9:
      return "wxyz";
  }
  return "";
}

vector<string> letterCombinations(string digits) {
  if (digits.empty()) {
    return vector<string>();
  }

  vector<string> result{""};
  for (char digit : digits) {
    string letters = numberToLetter(digit - '0');
    if (letters.empty()) {
      continue;
    }

    vector<string> newResult;
    for (char letter : letters) {
      for (string str : result) {
        newResult.push_back(str + letter);
      }
    }
    result = newResult;
  }

  return result;
}