Here is the implementation for Decode Ways (LeetCode ):
function numDecodings(s)
n := length of s
dp := array of size n + 1, all set to 0
dp[n] := 1
for i from n - 1 down to 0
if s[i] = '0' then
dp[i] := 0
else
dp[i] := dp[i + 1]
if i + 1 < n then
twoDigit := integer value of s[i..i+1]
if twoDigit >= 10 and twoDigit <= 26 then
dp[i] := dp[i] + dp[i + 2]
return dp[0]
The tricky part is handling '' correctly. A '' can never be decoded alone, so dp[i] stays when s[i] is ''. For all other digits, you take dp[i+1] (one digit) and optionally add dp[i+2] if the two-digit number falls in -. Trace through "" to verify: dp[3]=1, dp[2]=1, dp[1]=2, dp[0]=3.
Time complexity: .
Space complexity: , reducible to by tracking only the last two values.