[Leetcode Solution] Decode Ways

Analysis

• Problem itself is a typical dp problem however the test case could be pretty boring because some of them are weird because if the input string is a encoding message then how could it be a invalid string with 0 ways to decode
• Let f[i] denote the ways can be decoded of the first i characters 
• F[i] = F[i-1] + F[i-2] 
• //if the number consisted by str[i] and str[i-1] is a valid number 
• F[i] = F[i-1]
• //if the number consisted by str[i] and str[i-1] is not a valid number
• Notice the substring "00" appears in the test case which is nonsense

Note

Code