# **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` `值得再想`