Secret Number Notes

Mediumdynamic programmingAlso known as Decode Ways

Two friends pass notes in class using a simple code: every letter becomes its position in the alphabet, so A is 1, B is 2, and Z is 26. To make the notes harder to read, they write all the numbers together with no spaces. "KZ" becomes 1126.

The trouble is that 1126 could also be "AABF", "ALF" and a few more. Before guessing, the reader wants to know how many different messages a note could mean.

Your task

Write countReadings(note). note is a string of digits. Split it into pieces, where each piece is a number from 1 to 26 written without a leading zero, and return how many different splits there are.

So "10" and "20" are valid pieces, but "0", "05" and "27" are not. If the note cannot be split at all, return 0.

countReadings(note: string) → int

Examples

Example 1

Input

note = "1126"

Output

Why

The splits are 1-1-2-6 (AABF), 11-2-6 (KBF), 1-12-6 (ALF), 1-1-26 (AAZ) and 11-26 (KZ). The piece 126 is too big, so nothing else works.

Example 2

Input

note = "2105"

Output

Why

A 0 can never stand alone, so it must be the end of 10 or 20. Here it pairs with the 1 to make 10, which forces 2-10-5 (BJE). The split 21-0-5 fails because of the lone 0.

Constraints

1 ≤ note.length ≤ 60
note contains only the digits 0 to 9.
The answer is below 10¹³.

Start with brute force

Recursively cut off one or two digits from the front, check the piece is valid, and count the splits that reach the end. It is correct, but a note of sixty 1s has about 2.5 trillion readings, and the recursion walks through every one.

The waste: the number of readings of "the rest of the note from position 30" is the same no matter how you got there, yet the recursion recomputes it for every path that reaches position 30.

Hints

0 of 4 shown

Hint 1
Look at the end of 1126. The last piece of any reading is either the single digit 6 or the pair 26. What is left of the note in each case?
Hint 2
If the last piece is one digit, the rest is 112; if it is two digits, the rest is 11. Every reading of the full note is a reading of one of those prefixes plus that last piece. So you only need the counts for shorter prefixes.
Hint 3
Let ways[i] be the number of readings of the first i digits, with ways[0] = 1. Add ways[i - 1] when digit i alone is 1 to 9. Add ways[i - 2] when the last two digits form a number from 10 to 26.
Hint 4
Fill ways left to right. Watch the zeros: a single 0 adds nothing, and a pair starting with 0 (like 05) is not 10 to 26, so it adds nothing either. Only the last two values are needed at any time.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Every reading ends with a one-digit piece or a two-digit piece. So the readings of the first i digits are the readings of the first i - 1 (if the last digit is a valid piece) plus the readings of the first i - 2 (if the last two digits are a valid piece).

Trace "1126". ways for the empty prefix is 1.

"1": the digit 1 is valid. ways = 1.
"11": single 1 is valid (+1), pair 11 is valid (+1 from the empty prefix). ways = 2.
"112": single 2 is valid (+2), pair 12 is valid (+1). ways = 3.
"1126": single 6 is valid (+3), pair 26 is valid (+2). ways = 5.

For "2105" the zero matters: at "210" the single 0 adds nothing and the pair 10 adds the count for "2", which is 1. At "2105" the single 5 adds 1, and the pair 05 is not 10 to 26. Answer 1.

Reference solution

function countReadings(note) {
  let prev2 = 1; // readings of the prefix two digits back (empty prefix: 1)
  let prev1 = note[0] === "0" ? 0 : 1; // readings of the first digit
  for (let i = 1; i < note.length; i++) {
    let here = 0;
    if (note[i] !== "0") here += prev1;         // last piece is one digit
    const pair = Number(note.slice(i - 1, i + 1));
    if (pair >= 10 && pair <= 26) here += prev2; // last piece is two digits
    prev2 = prev1;
    prev1 = here;
  }
  return prev1;
}

def count_readings(note):
    prev2 = 1  # readings of the prefix two digits back (empty prefix: 1)
    prev1 = 0 if note[0] == "0" else 1  # readings of the first digit
    for i in range(1, len(note)):
        here = 0
        if note[i] != "0":
            here += prev1  # last piece is one digit
        pair = int(note[i - 1:i + 1])
        if 10 <= pair <= 26:
            here += prev2  # last piece is two digits
        prev2, prev1 = prev1, here
    return prev1

TimeO(n)One pass, checking one single digit and one pair per position.

SpaceO(1)Only the last two counts are kept.

Learn the idea: 1D Dynamic Programming DP on Strings

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code