# LeetCode Medium 17. Letter Combinations of a Phone Number

tags: leetcode

問題

• Explore
• Problems

$2$から$9$までの数を含む文字列が与えられたとき, その数が表現できるであろう全てのありうる文字の順列を返せ

数字から文字への対応(電話のボタンのような)は下のように与えられている. $1$はどんな文字列とも対応しないことを注意せよ.

注意:

解答は辞書順でなくても良い

解法

まずは数字を文字と対応させます

数字が添字になった時に, その数字に対応した文字列となる配列を用意します

• strListとしておきます
• 答えと成る配列に空文字列を入れます
  • この中に入っている要素にstrListの文字列から文字を加えていきます
• 与えられる文字列digitsから数字を取り出していき, それを整数型にして添字として利用します(連想配列を使っても良いです)
  • そして文字列を取り出します
• 答えとなる配列のそれぞれの要素にこの時に得られた文字列の文字を加えたものをtmpなどと名前の付いた一時的な配列に格納します
• そして, 格納した配列と答えと成る配列を交換します

計算量

与えられる数字のうち, $3$文字の文字列に対応するもの, $4$文字の文字列に対応するものをそれぞれn, mとします

• 空間計算量
  • $O(3^{n} \cdot 4^{n})$
• 時間計算量
  • $O(3^{n} \cdot 4^{n})$

Python

class Solution:
  def letterCombinations(self, digits: str) -> List[str]:
    if not digits:
      return []
    
    res = [""]
    str_list = {
      2 : "abc",
      3 : "def",
      4 : "ghi",
      5 : "jkl",
      6 : "mno",
      7 : "pqrs",
      8 : "tuv",
      9 : "wxyz"
    }
    
    for i in range(len(digits)):
      num = int(digits[i])
      candidate = str_list[num]
      tmp = []
      for j in range(len(candidate)):
        for k in range(len(res)):
          tmp.append(res[k] + candidate[j])
      res, tmp = tmp, res
      
    return res

C++

class Solution {
public:
  vector<string> letterCombinations(string digits) {
    if (digits.empty()) {
      return {};
    }
    vector<string> res;
    static const vector<string> strList = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    res.push_back("");

    for (int i = 0; i < digits.size(); i++) {
      int num = digits[i] - '0';
      const string& candidate = strList[num];
      vector<string> tmp;
      for (int j = 0; j < candidate.size(); j++) {
        for (int k = 0; k < res.size(); k++) {
          tmp.push_back(res[k] + candidate[j]);
        }
      }
      res.swap(tmp);
    }
    return res;
  }
};