Module 23 · Dynamic Programming I: One-Dimensional State

226. Decode Ways

Bridge · Download this solution · All solutions and shared helpers

Problem

Count decodings of an ASCII digit string under 1->A through 26->Z. Codes have no leading zero; '0' alone is invalid, while '10' and '20' are valid. Return zero for an empty message under this public contract. Different partitions into valid codes count separately.

Examples

Example 1

decode_ways("226")
=> 3

Three valid code partitions produce three decodings.

Example 2

decode_ways("06")
=> 0

A leading zero cannot begin any code.

Example 3

decode_ways("10")
=> 1

Only the two-digit code is valid.

Example 4

decode_ways("")
=> 0

The public empty-message result is explicitly zero.

Reveal the worked solution and reasoning

Why this mechanism works

Use prefix length as the state. A decoding of the first i digits ends with either a valid one-digit code or a valid two-digit code. Their predecessor prefix counts add because the final code lengths distinguish the classes. The internal empty-prefix count is one even though the public empty-message result is defined as zero.

State and boundaries

Before processing length i, previous=dp[i-2] and current=dp[i-1]. dp[0]=1 represents one way to decode an already-consumed empty prefix.

Protocol

Handle empty text.
Initialize dp[0]=1 and dp[1] from the first digit.
For each later prefix add current for a nonzero final digit.
Add previous for a final pair between 10 and 26.
Roll states.

Visualization

'226' -> 2|2|6, 22|6, 2|26
prefix counts: dp[0]=1, dp[1]=1, dp[2]=2, dp[3]=3

Python implementation

def decode_ways(text):
    if not text:
        return 0
    previous, current = 1, int(text[0] != '0')
    for i in range(2, len(text) + 1):
        ways = current if text[i - 1] != '0' else 0
        if 10 <= int(text[i - 2:i]) <= 26:
            ways += previous
        previous, current = current, ways
    return current

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

decode_ways("226")

L2 decode_ways: if not text:
text='226'

L4 decode_ways: previous, current = 1, int(text[0] != '0')
text='226'; previous=1; current=1

L5 decode_ways: for i in range(2, len(text) + 1):
text='226'; previous=1; current=1; i=2

L6 decode_ways: ways = current if text[i - 1] != '0' else 0
text='226'; previous=1; current=1; i=2; ways=1

L8 decode_ways: ways += previous
text='226'; previous=1; current=1; i=2; ways=2

L9 decode_ways: previous, current = current, ways
text='226'; previous=1; current=2; i=2; ways=2

L5 decode_ways: for i in range(2, len(text) + 1):
text='226'; previous=1; current=2; i=3; ways=2

L8 decode_ways: ways += previous
text='226'; previous=1; current=2; i=3; ways=3

L9 decode_ways: previous, current = current, ways
text='226'; previous=2; current=3; i=3; ways=3

Result: 3. Three valid code partitions produce three decodings.

decode_ways("06")

L2 decode_ways: if not text:
text='06'

L4 decode_ways: previous, current = 1, int(text[0] != '0')
text='06'; previous=1; current=0

L5 decode_ways: for i in range(2, len(text) + 1):
text='06'; previous=1; current=0; i=2

L6 decode_ways: ways = current if text[i - 1] != '0' else 0
text='06'; previous=1; current=0; i=2; ways=0

L9 decode_ways: previous, current = current, ways
text='06'; previous=0; current=0; i=2; ways=0

Result: 0. A leading zero cannot begin any code.

Why the solution is correct

Removing the final valid code maps each decoding uniquely to a predecessor decoding. The one- and two-digit validity tests include exactly the permitted codes, so the recurrence counts all decodings without duplication. Ascending prefix length supplies complete predecessor counts.

Time and space

O(n) small-substring checks and additions, using O(1) integer variables. Exact count bit lengths can grow with n.

Common mistakes

Treating zero as a standalone code admits invalid messages. Setting internal dp[0] to zero removes valid two-digit decodings such as '10'.

Reasoning card

State: Before processing length i, previous=dp[i-2] and current=dp[i-1]. dp[0]=1 represents one way to decode an already-consumed empty prefix.

Invariant: dp[i] counts decodings of the first i characters.

Decision to rehearse: Add ways from valid one-digit and two-digit predecessors.

Finish: Roll states

Transfer exercise

Allow '*' as an unknown digit and count the valid one- and two-character interpretations for each transition.