Decode Ways

Decode Ways is a classic dynamic programming problem often asked in Amazon interviews, where you determine how many ways a string of digits can be decoded using the mapping 1→A, 2→B, ..., 26→Z. A digit string like "226" has three decodings: "BZ" (2,26), "VF" (22,6), or "BBF" (2,2,6).[1][6]

Problem Statement

A message containing letters from A-Z can be encoded into numbers using the mapping where 'A' → "1", 'B' → "2", ..., 'J' → "10", ..., 'Z' → "26". Given a non-empty string s of digits, return the number of ways to decode it. The string only contains digits, and decoding must follow valid letter mappings—no leading zeros except for "0" itself (which is invalid).[6][1]

Examples

• Input: s = "12" → Output: 2 (decodings: "AB" (1,2) or "L" (12)).[1]
• Input: s = "226" → Output: 3 (decodings: "BZ" (2,26), "VF" (22,6), "BBF" (2,2,6)).[1]
• Input: s = "06" → Output: 0 (invalid, as "06" cannot be decoded).[3][1]

Constraints

• 1 ≤ s.length ≤ 100
• s contains only digits '0'-'9'
• s[0] does not equal '0' in valid cases, but strings starting with '0' return 0.[6][1]