Decoded Ways

The key thinking is to use Fibonocci + DP

Every time we consider the last two digits. For example, string = 211, we only consider 11.
If the last digit, 1, is taken individually, we know that the combination regarding to this arrangement is dp[i-1]
if the last two digit, 12, is taken, we know that the combination regarding to this arrangement is dp[i-2]
So, the total combination of i is dp[i-1] + dp[i-2]

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 0 or s[0] == '0':
            return 0

        prev1, prev2 = 1, 1

        for i in range(1, len(s)):
            // '0' cannot be separated, so prev1 is 0
            if s[i] == '0':
                prev1 = 0

            if int(s[i-1] + s[i]) <= 26:
                tmp = prev1 + prev2
                prev2 = prev1
                prev1 = tmp
            else:
                prev2 = prev1


        return prev1