スポンサーリンク

【LeetCode】17. Letter Combinations of a Phone Number 解答・解説【Python】

スポンサーリンク
スポンサーリンク
この記事は約4分で読めます。

 

問題

原文

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.

 

Example 1:

Example 2:

Example 3:

 

Constraints:

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

 

内容

2~9の数字を含む文字列が与えられます。

表すことができる全ての組み合わせを順序を問わず返してください。

数字と文字列の対応(携帯電話のボタンのような)は以下(問題文の画像)の通りです。

注意:1はどの文字列にも対応していません。

 

 

制約

・digitsの長さは0~4の範囲

→入力されるdigitsがない場合の考慮が必要

→digitsは4までなので、1つの組み合わせでの最大は4*4*4*4=256個になりそう

※7,9は文字列が4つある

・digits[i]は2~9の範囲

 

 

※正しくない可能性があります。

 

解答

解答1:Python, backtracking

 

 

・digits=23の場合のイメージ

backtrack(“”,23): ※関数letterCombinationsでの呼び出し

※以降は全て関数backtrack内での動作

for letter in “abc”:

➀backtrack(a,3):

→for letter in “def”:

→→backtrack(ad,[]):

→→→answer = (ad)

→→backtrack(ae,[]):

→→→answer = ad,ae)

→→backtrack(ae,[]):

→→→answer = (ad,ae,af)

 

②backtrack(b,3):

→for letter in “def”:

→→backtrack(bd,[]):

→→→answer = (ad,ae,af,bd)

→→backtrack(be,[]):

→→→answer = (ad,ae,af,bd,be)

→→backtrack(bf,[]):

→→→answer = (ad,ae,af,bd,be,bf)

 

③backtrack(c,3):

→for letter in “def2:

→→backtrack(cd,[]):

→→→answer = (ad,ae,af,bd,be,bf,cd)

→→backtrack(ce,[]):

→→→answer = (ad,ae,af,bd,be,bf,cd,ce)

→→backtrack(cf,[]):

→→→answer = (ad,ae,af,bd,be,bf,cd,ce,cf)

 

 

 

 

メモ・参考・感想

 

 

 

前:40. Combination Sum II

 

次:55. Jump Game

 

LeetCode 解答・解説記事一覧

コメント