動的計画法で数字だけの暗号を文字に戻す読み方を数える

動的計画法 (DP)問題 134

A を 1、B を 2、…、Z を 26 と置き換えて区切りを消した数字の列が、何通りの文字の並びに読めるかを数えます。最後の 1 桁か 2 桁で場合を分け、前の 2 つの答えを足していく練習です。

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

問題

英大文字を、A は 1、B は 2、…、Z は 26 と数に置き換え、区切りを消してつなげた暗号があります。数字だけの文字列 digits を受け取り、元の英大文字の並びとして読める読み方が何通りあるかを返す関数を書いてください。

1 文字は、1 桁 (1 から 9) か 2 桁 (10 から 26) の数です
0 で始まる区切り (0 だけ、05 など) は、どの文字にも当たりません
どう区切っても読めないときは 0 を返します
digits の長さは 1 以上 100 以下で、答えは 2^31 より小さくなるものとします

入力と出力の例

例 1

1-2-2-6 (ABBF)、12-2-6 (LBF)、1-22-6 (AVF)、1-2-26 (ABZ)、12-26 (LZ) の 5 通りです。

digits = "1226"

例 2

0 は 1 文字にならないので、20 と区切るしかありません。20-5 (TE) の 1 通りです。

digits = "205"

例 3

0 は前の 3 とつないでも 30 で、26 を超えます。読めないので 0 です。

digits = "301"

面接での聞かれ方

面接では、階段の上り方の数え方に「0 の扱い」という罠を足した形で出されます。

「A を 1、Z を 26 とした暗号の数字列は、何通りに読めますか」
書く前に「06 は 6 と読めますか？」「読めないときは何を返しますか？」と確かめられるかを見られます
書き終えると「0 がたくさん入った例で確かめてください」と、端の場合を手でたどるよう求められます

正しい形は階段と同じですが、0 の扱いで落とす人がとても多い問題です。

ヒント

まだ開いていません

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

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

アルゴリズムのチートシートの「動的計画法 (DP)」に、この型の要点を表とコードでまとめています。

動的計画法は、途中の答えを覚えておいて、同じ計算をやり直さない書き方です。漸化式で言い直せる問題が多いです。

数学1-2 シグマと漸化式
CS2-9 動的計画法

まず考える手順

段 1

区切り方を全部試すと、毎回「1 桁で切るか 2 桁で切るか」を選ぶので、組み合わせは長さに対して指数的に増えます。100 桁では終わりません。

段 2

前から i 桁を読む読み方の数を ways[i] と置きます。最後の 1 文字は、i 桁目の 1 桁だけか、i - 1 桁目と i 桁目の 2 桁かのどちらかです。1 桁が 1 から 9 なら ways[i-1] 通りを足し、2 桁が 10 から 26 なら ways[i-2] 通りを足します。

段 3

ways[0] (何も読まない) を 1 と置くと、決まりどおりに先頭から進められます。0 の桁は 1 桁としては足さず、前の桁と組んだ 10 か 20 のときだけ 2 桁として足します。どちらも足せなければ ways[i] は 0 になり、その後もずっと 0 です。

段 4

使うのは前の 2 つだけなので、変数 2 つを持ち歩けば足ります。

解答

Python

def decode_count(digits):
    far, near = 1, 1
    prev = "0"
    for d in digits:
        here = 0
        if d != "0":
            here += near
        pair = prev + d
        if "10" <= pair <= "26":
            here += far
        far, near = near, here
        prev = d
    return near

JavaScript

function decodeCount(digits) {
  let far = 1;
  let near = 1;
  let prev = "0";
  for (const d of digits) {
    let here = 0;
    if (d !== "0") {
      here += near;
    }
    const v = Number(prev + d);
    if (v >= 10 && v <= 26) {
      here += far;
    }
    far = near;
    near = here;
    prev = d;
  }
  return near;
}

Go

func decodeCount(
	digits string,
) int {
	far, near := 1, 1
	prev := byte('0')
	b := []byte(digits)
	for _, d := range b {
		here := 0
		if d != '0' {
			here += near
		}
		v := int(prev-'0') * 10
		v += int(d - '0')
		if v >= 10 && v <= 26 {
			here += far
		}
		far, near = near, here
		prev = d
	}
	return near
}

near は直前までの読み方の数、far はその 1 つ前です。prev は 1 つ前の桁で、始めは 0 にしておきます。こうすると 1 桁目では 2 桁の組が 0 で始まり、10 以上にならないので、2 桁の場合を数えません。2 桁が 10 以上かを確かめることで、05 のような 0 で始まる区切りも外しています。Python は 2 桁の文字列どうしを辞書の順で比べています。どちらも 2 文字なので、数として比べるのと同じ結果です。

計算量

時間は O(n) です (n は digits の長さ)。1 桁ずつ 1 回見ます
使う記憶は O(1) です。持つのは変数 2 つだけです
ways の表を全部持つ書き方も時間は同じで、記憶が O(n) になります

よくある間違い

0 を 1 桁の文字として数える。 1 桁は 1 から 9 だけです。例 3 で 0 でない数を返したら、この間違いです
2 桁を 26 以下かだけで確かめる。 05 は 5 として 26 以下なので、10 以上かも見ないと "105" を 2 通りと数えてしまいます。答えは 10-5 の 1 通りです
文字列をはじめに整数へ直す。 "06" を整数にすると先頭の 0 が消えて 6 になり、1 通りと数えてしまいます。0 で始まる区切りは読めないので 0 です。桁は文字のまま 1 つずつ見ます
続く 0 を見落とす。 "100" は、2 桁目までは 10 の 1 通りでも、3 桁目の 0 は 1 桁にも、前と組んだ 00 にもならないので 0 です

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

main.py

def decode_count(digits: str) -> int:
    """
    Goal: 何を返すか

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

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

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


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

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