Leetcode 91 - decode ways - analysis

Leetcode 91 - Decode ways - analysis

91. Decode Ways - hard level - medium level 

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 "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

1 - 26 


1  2    5  1  5
1  25      1
           15
12      5  1
           15
   

Output: the total number of ways to decode it
Example:
12
could be decoded as

AB

L=> 12

12=> message

could be decoded as L and AB

output=> 12

1    2
i    j
while loop
less 26
first*10+second

1     2
1
2

1238  712
xyz 

top down
then cache results in a table  - number of ways to decode dp[SIZE] -> dp[size - 1] 

if num>=1 num<=26

work on test case 1238712, build up a dynamic programming lookup table - 
                                                                 i->7
0        1                         2   <- index          3       3
1        2                           3<-dp table//
1        2                           3                   8       7       1              2    dp[index - ] 
 
1       12                         123                1238    12387   123871        1238712    - 12  -> current 2 do it alone + 1, previous 12 -> 
-------------------------------------------------------


1       dp[0] + lookup("")    dp[1](3 is C)   + dp[0] (since 23 <= 26)
           
         check                 3 - c  dp[i-1] +     23<=26?      dp[i - 2] : 0
         2 -  B - dp[0]
         12 - L -decode("")      dp[i] = dp[i - 1] + (23<=26)? dp[i -2]:0;  i>= 1
 
1        2                       2 + 1 = 3             3        3         3            3 + 3 = 6          
 -------------------------------------------------------------->bottom up dynamic programming             

Analysis:
                 
if value is 1-9, dp[i]+=dp[i-1] i >=1
if check char(nums[i-1]* 10 +nums[i]) <= 26 and >0 so check if it's a lower case letter
    then dp[i]+=(i == 1)? 1 : dp[i-2]