Decode Ways – Solution & Complexity

• The choice at index i only affects the remaining suffix after consuming one or two digits.
• That makes this a natural dynamic-programming problem over suffixes.

• A recursive search tries one-digit and two-digit decodes whenever they are valid.
• Without memoization, repeated suffixes explode exponentially.

• If s[i] is 0, there are 0 ways from that position.
• Otherwise, start with the number of ways from i + 1 (taking one digit).
• If s[i:i+2] is between 10 and 26, also add the number of ways from i + 2.

A right-to-left scan only needs the next two DP values, so the suffix DP compresses to constant space.

• Treating 0 as a standalone letter, which is never allowed.
• Allowing any two-digit number under 30; only 10 through 26 are valid pairs.
• Follow-up: when * is introduced, the recurrence stays similar but each branch contributes multiple counts instead of just one.