Dynamic Programming
LC #91Medium
Decode Ways
Dynamic Programming
MetaAmazonGoogleBloombergMicrosoftProblem
A string of digits can be decoded as letters (1→A, 2→B, ..., 26→Z). Count the number of ways to decode it.
stringdynamic-programming
Constraints
- ›1 ≤ s.length ≤ 100
- ›s contains only digits
- ›s may contain leading zeros
Example
Input
s = "226"Output
3Why
"226" can be decoded as "BBF"(2,2,6), "BZ"(2,26), or "VF"(22,6)