バックトラックで電話のボタンの数字から作れる文字の並びを全部集める

バックトラック問題 125

昔の携帯電話のボタンには、数字ごとに英字がいくつか割り当てられています。押した数字の並びから作れる英字の並びを、決まった順で全部集める練習です。

海外で定番の問題リスト 4 本には入っていません

問題

昔の携帯電話では、数字のボタンに次の英小文字が割り当てられていて、同じボタンで違う字を打てました。

2 は abc、3 は def、4 は ghi、5 は jkl
6 は mno、7 は pqrs、8 は tuv、9 は wxyz

押した数字の並びを文字列 digits で受け取ります。数字ごとに割り当ての字を 1 つずつ選んでつなげた文字列を、選び方の全部について集め、並びにして返す関数を書いてください。

返す順は辞書の順です。1 字目を上の割り当ての順 (たとえば 7 なら p、q、r、s の順) に選び、1 字目が同じ物どうしは 2 字目を同じ決まりで選びます
digits が空なら、空の並び [] を返します
digits の長さは 0 以上 4 以下で、字はどれも "2" から "9" のどれかです

入力と出力の例

例 1

5 は j、k、l、8 は t、u、v です。3 かける 3 で 9 通りです。

digits = "58"

["jt", "ju", "jv", "kt", "ku", "kv", "lt", "lu", "lv"]

例 2

数字が 1 つなら、割り当ての字がそのまま 1 字ずつ並びます。9 は 4 字です。

digits = "9"

["w", "x", "y", "z"]

例 3

何も押していないので、作れる文字列はありません。

digits = ""

[]

面接での聞かれ方

面接では、短く次のように渡されることが多いです。

「電話の数字の並びから、作れる文字の組み合わせを全部返してください」
書き終えると「何通りになりますか？計算量は？」と、答えの数から計算量を言えるかを聞かれます
「再帰を使わずに書けますか？」と、並びを 1 段ずつ広げる書き方を聞かれることもあります

空の入力で [] を返すのか [""] を返すのかを最初に確かめておくと、端で迷いません。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「再帰と木」に、この型の要点を表とコードでまとめています。

再帰は、同じ形の小さい問題に分けて自分を呼ぶ書き方です。木の深さや、全部の組み合わせを数える問題で使います。

まず考える手順

段 1

数字の数が決まっていれば、その数だけ for を入れ子にすれば書けます。2 桁なら 2 重、3 桁なら 3 重です。けれども数字の数は入力で変わるので、入れ子の深さを決めておけません。

段 2

「i 桁目の字を選んだら、i + 1 桁目を選ぶ」を、自分を呼ぶ関数 (再帰) にします。引数は、いま何桁目かと、ここまでに選んだ字の並びです。全部の桁を選び終えたら、その並びを答えに足して戻ります。これで深さが入力で変わっても書けます。

段 3

各桁では、割り当ての字を前から順に試します。前から順に試すので、答えは自然に辞書の順に並び、あとで並べ替える必要はありません。割り当ては辞書 (Go は map、または 10 個の並び) に持っておきます。

段 4

digits が空のとき、そのまま再帰に入ると「全部の桁を選び終えた」と見て空の文字列を 1 つ足してしまいます。最初に空かどうかを確かめて、[] を返します。

解答

Python

KEYS = {
    "2": "abc", "3": "def",
    "4": "ghi", "5": "jkl",
    "6": "mno", "7": "pqrs",
    "8": "tuv", "9": "wxyz",
}


def phone_letters(digits):
    if not digits:
        return []
    out = []

    def walk(i, s):
        if i == len(digits):
            out.append(s)
            return
        d = digits[i]
        for c in KEYS[d]:
            walk(i + 1, s + c)

    walk(0, "")
    return out

JavaScript

const KEYS = {
  2: "abc", 3: "def",
  4: "ghi", 5: "jkl",
  6: "mno", 7: "pqrs",
  8: "tuv", 9: "wxyz",
};

function phoneLetters(digits) {
  if (digits === "") {
    return [];
  }
  const out = [];
  const walk = (i, s) => {
    if (i === digits.length) {
      out.push(s);
      return;
    }
    const d = digits[i];
    for (const c of KEYS[d]) {
      walk(i + 1, s + c);
    }
  };
  walk(0, "");
  return out;
}

Go

var keys = map[byte]string{
	'2': "abc", '3': "def",
	'4': "ghi", '5': "jkl",
	'6': "mno", '7': "pqrs",
	'8': "tuv", '9': "wxyz",
}

func phoneLetters(
	digits string,
) []string {
	out := []string{}
	if digits == "" {
		return out
	}
	var walk func(int, string)
	walk = func(i int, s string) {
		if i == len(digits) {
			out = append(out, s)
			return
		}
		d := digits[i]
		for _, c := range keys[d] {
			walk(i+1, s+string(c))
		}
	}
	walk(0, "")
	return out
}

ここまでの字を文字列のまま引数で渡しているので、呼び出しから戻ったときに元へ戻す (取り消す) 手間がありません。文字列をつなぐたびに新しい文字列ができますが、長さは 4 字までなので気にしなくてかまいません。

計算量

時間は O(4^n × n) です。n は数字の数で、1 つの数字は多くて 4 字なので答えは 4^n 通りまで、1 つを作るのに n 字をつなぎます
使う記憶は、答えを除くと O(n) です。再帰の深さが n です。答えそのものは O(4^n × n) あります

よくある間違い

空の入力で [""] を返す。 再帰に入る前に空を確かめないと、空の文字列が 1 つ入った並びを返します。この問題では [] です
7 と 9 を 3 字にする。 7 は pqrs、9 は wxyz の 4 字です。割り当ての表を書くときに 1 字落とすと、答えが足りなくなります
桁ごとに for を入れ子にする。入力の長さで入れ子の深さが変わるので、決まった数の for では書けません
選んだ字の並びを使い回して、答えに入れたあと書き換える。並び (Python の list や JavaScript の配列) を答えにそのまま入れると、あとの書き換えで中身が変わります。答えに入れるときは文字列にします

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def phone_letters(digits: str) -> list[str]:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(phone_letters("58"))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します