Decode Ways
A message containing letters from
A-Z
is being encoded to numbers using the following mapping:'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message
Given encoded message
"12"
, it could be decoded as "AB"
(1 2) or "L"
(12).
The number of ways decoding
"12"
is 2.
Solution: DP. Use chk[n] to denote the number of decode ways:
chk[n] = chk[n-1]*IsValid(s[n]) + chk[n-2]*IsValid(s[n-1], s[n])
Comments
Post a Comment