---
# System prepended metadata

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

---

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

## Approach
![](https://i.imgur.com/pf599GX.png)

* 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<sup>th</sup> 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
``` python
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)}")
```