Thank you so much for this clean and intuitive solution!!

I wrote some notes for myself reference, hope it might help someone to understand this solution.

dp[i]: represents possible decode ways to the ith char(include i), whose index in string is i-1

Base case: dp[0] = 1 is just for creating base; dp[1], when there's one character, if it is not zero, it can only be 1 decode way. If it is 0, there will be no decode ways.

Here only need to look at at most two digits before i, cuz biggest valid code is 26, which has two digits.

For dp[i]: to avoid index out of boundry, extract substring of (i-1,i)- which is the ith char(index in String is i-1) and substring(i-2, i)

First check if substring (i-1,i) is 0 or not. If it is 0, skip it, continue right to check substring (i-2,i), cuz 0 can only be decode by being together with the char before 0.

Second, check if substring (i-2,i) falls in 10~26. If it does, means there are dp[i-2] more new decode ways.

Time: should be O(n), where n is the length of String

Space: should be O(n), where n is the length of String