# [Decode Ways](https://leetcode.com/problems/decode-ways/)
###### tags: `Leetcode`, `Medium`, `Dynamic Programming`

## Approach

* Initialize a `dp` array of the same size as the size of the string
* Set the default value of the last index value of `dp` to `1`
* Iterate in reverse i.e. from the second last index to the 0^th index
* `dp[index] = dp[index+1]` for every index position
* If `index + 1` is in the range of `len(s)` and if `s[index] == '1'` or if `s[index] == 2 and s[index + 1] is any of 0, 1, 2, 3, 4, 5, 6` then it means that we can partition the value at this index in two ways(Refer to the image above):
1. This index value as it is and the remaining digits
***From the image above (1, decodings of 26)***
2. This index value and `index + 1` value as a letter and the remaining digits
***From the image above (12, decodings of 6)***
* In the above case, `dp[index] = dp[index] + dp[index + 2]`

* Return `dp[0]`

## Asymptotic Analysis
### Time Complexity: **O(N)**
### Space Complexity: **O(N)**

## Code

class DecodeWays:
    def num_decodings(self, s: str) -> int:
        dp = [0] * (len(s) + 1)
        dp[len(s)] = 1
        for index in range(len(s) - 1, -1, -1):
            if s[index] == '0':
                continue
            dp[index] = dp[index + 1]
            if (index + 1) < len(s) and \
                    (s[index] == '1' or 
                     (s[index] == '2' and s[index + 1] in '0123456')):
                dp[index] += dp[index + 2]
        return dp[0]


input_string = "2611055971756562"
decode = DecodeWays()
print(f"Number of decodings for the string '{input_string}' = {decode.num_decodings(input_string)}")