---
# System prepended metadata

title: '**Leetcode筆記(Decode Ways)**'
tags: [值得再想, medium, dynamic programming, leetcode]

---

# **Leetcode筆記(Decode Ways)**


:::info
:information_source: 題目 : Decode Ways, 類型 : dynamic programming , 等級 : medium
日期 : 2023/04/23，2023/06/13，2023/07/18，2024/09/30
:::


### 嘗試

```python
class Solution:
    def numDecodings(self, s: str) -> int:
        res = 0

        def valid_number(num, j):
            if num == 0 and j != len(s) - 1:
                res = 0
                return 
            if 1 <= num and num <= 26 and j == len(s):
                res += 1
                return
        
        for i in range(len(s)):
            valid_number(int(s[i]), i)
        for i in range(0, len(s), 2):
            valid_number(int(s[i]), i)
        
        return res
```
2023/06/13
dp[i]代表 解析s[:i] (從起頭到目前的i為止) 字符串所有可能的組成方式數目
```python
dp[i] = dp[i-1] if s[i] != '0'
        + dp[i-2] if '9' < s[i-2:i] < '27'
```
```python
class Solution:
    def numDecodings(self, s: str) -> int:
        dp = [0] * (len(s) + 1)
        dp[0] = 1

        for i in range(1, len(dp)):
            if 0 < int(s[i - 1]) < 10:
                dp[i] = dp[i - 1]
            if i >= 2 and 10 <= int(s[i - 2 : i]) <= 26:
                dp[i] += dp[i - 2]
        
        return dp[len(s)]
```
2023/07/18
**如果可以單個存在，就把上一項加起來，如果可以雙個存在，就把前前一項加起來**
```python
class Solution:
    def numDecodings(self, s: str) -> int:
        # 想法 : 如果可以單個存在 就把上一項加起來
        #       如果可以雙個存在 就把前前一項加起來
        dp = [0] * (len(s) + 1)
        dp[0] = 1

        for i in range(1, len(s) + 1):
            if 0 < int(s[i - 1]) < 10:
                dp[i] = dp[i] + dp[i - 1]
            if i >= 2 and 10 <= int(s[i - 2] + s[i - 1]) <= 26:
                dp[i] = dp[i] + dp[i - 2]
        
        return dp[len(s)]
```
2024/09/30
```
class Solution:
    def numDecodings(self, s: str) -> int:
        dp = [0] * (len(s) + 1)
        dp[0] = 1

        for i, c in enumerate(s):
            n = int(c) 
            if 0 < n <= 9:
                dp[i + 1] = dp[i]
            if i > 0:
                pre_n = int(s[i - 1])
                if 10 <= (pre_n * 10 + n) <= 26:
                    dp[i + 1] += dp[i - 1]

        return dp[-1]
```

---
### **優化**

对于”226”：

令dp数组为[0,0,0,0]，初始化为[1,0,0,0]；

从第一个位置开始，输入为”2”，不为”0”，所以dp数组为[1,1,0,0]；

第2个位置，输入为”2”，不为”0”，所以dp数组为[1,1,1,0]；此时前两位数字是”22”，满足区间，所以变为[1,1,2,0]；

第3个位置，输入为”6”，不为”0”，所以dp数组为[1,1,2,2]，2為直接延續前面的數字；此时前两位数字是”26”，满足区间，所以再加一種可能变为[1,1,2,3]。

對於"2326"
令dp数组为[0,0,0,0,0]，初始化为[1,0,0,0,0]；

从第一个位置开始，输入为”2”，不为”0”，所以dp数组为[1,1,0,0,0]；

第2个位置，输入为”3”，不为”0”，所以dp数组为[1,1,1,0,0]；此时前两位数字是”23”，满足区间，所以变为[1,1,2,0,0]；

第3个位置，输入为”2”，不为”0”，所以dp数组为[1,1,2,2,0]，2為直接延續前面的數字；

第4个位置，输入为”6”，不为”0”，所以dp数组为[1,1,2,2,2]；此时前两位数字是”26”，满足区间，所以变为[1,1,2,2,4]，跨一行添加前面的2進來；

时间复杂度为O(n)，空间复杂度也为O(n)

```python
class Solution:
    def numDecodings(self, s: str) -> int:
        # 需要多創一個 並把它初始設定為1
        dp = [0] * (len(s) + 1)
        dp[0] = 1 # 第零格

        for i in range(1, len(dp)): # 從第一格開始

            # 考慮一位數1-9 (0只能在十位數的後面項)
            # 事實上是考慮第0個數字(s[0]) 放到第一格dp[1]
            if int(s[i - 1]) != 0:
                # 把後面的數移到前面
                dp[i] = dp[i - 1]
            
            # 考慮兩位數10-26
            # s[i - 2 : i]為上一位加現在這一位
            if i != 1 and int(s[i - 2 : i]) >= 10 and int(s[i - 2 : i]) <= 26:
                dp[i] += dp[i - 2]
            
        return dp[-1]
```
---


**:warning: 錯誤語法** 
:::warning

:::


**:thumbsup:學習** 
:::success

:::

**思路**


**講解連結**
https://blog.csdn.net/fuxuemingzhu/article/details/82120874
https://www.youtube.com/watch?v=To5-jVXXbvI&ab_channel=Peter%E5%88%B7Leetcode
Provided by. Peter刷Leetcode

###### tags: `dynamic programming` `medium` `leetcode` `值得再想`