本文主要是介绍算法第十三天-解码方法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
解码方法
题目要求
解题思路
来自【宫水三叶】
基本分析
我们称一个解码内容为一个item
。
根据题意,每个item
可以由一个数字组成,也可以由两个数字组成。
数据范围为100,很具有迷惑性,可能会有不少同学会想使用DFS进行暴力搜索。
我们可以大致分析一下这样子的做法是否可行:不失为一般性的考虑字符串s
中的任意位置i
,位置i
既可以作为一个独立item
,也可以与上一位置组成新item
,那么相当于每个位置都有两种分割选择(先不考虑分割结果的合法性问题),这样子做法的复杂度是 O ( 2 n ) O(2^n) O(2n)的,当n
范围是100时,远超我们计算机单秒运算量 ( 1 0 7 ) (10^7) (107)。及时我们将[判断分割结果是否合法]的操作放到暴力搜索过程中做剪枝,也与我们的单秒运算量相差很远。
递归的方法不可行,我们需要考虑递推的解法。
动态规划
这其实时一道字符串类的动态规划题,不难发现对于字符串s
的某个位置i
而言,我们只关心[位置i
自己能否形成独立item
]和[位置i
能够与上一位置(i-1
)能否形成item
],而不关心i-1
之前的位置。
有了以上分析,我们可以从前往后处理字符串s
,使用一个数组记录以字符串s
的每一位作为结果的解码方案数。即定义 f [ i ] f[i] f[i]为考虑前i个字符的解码方案数。
对于字符串s
的任意位置i
而言,其存在三种情况:
- 只能由位置
i
的单独作为一个item
,设为a
,转移的前提是a
的数值范围为[1,9],转移逻辑为f[i] = f[i-1]. - 只能由位置
i
的与前一位置(i-1)共同作为一个item
,设为b
,转移的前提时b
的数值范围为[10,26],转移逻辑为f[i] = f[i-2] - 位置
i
既能作为独立item
也能与上一位置形成item
,转移逻辑为f[i] = f[i-1] +f[i-2]
因此,我们有如下转移方程:
{ f [ i ] = f [ i − 1 ] , 1 ≤ a ≤ 9 f [ i ] = f [ i − 2 ] , 10 ≤ b ≤ 26 f [ i ] = f [ i − 1 ] + f [ i − 2 ] , 1 ≤ a ≤ 9 , 10 ≤ b ≤ 26 \left\{\begin{aligned} f[i] = f[i-1],1\le a \le 9\\ f[i] = f[i-2],10\le b \le 26\\ f[i] = f[i-1]+f[i-2],1\le a \le 9,10\le b \le 26\\ \end{aligned} \right. ⎩ ⎨ ⎧f[i]=f[i−1],1≤a≤9f[i]=f[i−2],10≤b≤26f[i]=f[i−1]+f[i−2],1≤a≤9,10≤b≤26
其他细节:由于本题存在前导零,而前导零属于无效item
。可以进行特判,但个人习惯往字符串头部追加空格作为哨兵,追加空格既可以避免讨论前导零,也能使下标从1开始,简化f[i-1]
等负数下标的判断。
代码
class Solution:def numDecodings(self, s: str) -> int:n = len(s)s = ' ' + sf =[0] *(n+1)f[0]=1for i in range(1,n+1):a = ord(s[i])-ord('0')b = (ord(s[i-1]) -ord('0')) * 10 + ord(s[i])-ord('0')if 0<a<=9:f[i] =f[i-1]if 10<=b<=26:f[i] +=f[i-2]return f[n]
复杂度分析
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( n ) O(n) O(n)
空间优化
不难发现,我们转移f[i]时只依赖f[i-1] 和 f[i-2]两个状态。因此我们可以采用与[滚动数组]类似的思路,只创建长度为3的数组,通过取余的方式来复用不再需要的下标。
代码
class Solution:def numDecodings(self, s: str) -> int:n = len(s)s = ' ' + sf = [0] * 3f[0] = 1for i in range(1,n + 1):f[i % 3] = 0a = ord(s[i]) - ord('0')b = ( ord(s[i - 1]) - ord('0') ) * 10 + ord(s[i]) - ord('0')if 1 <= a <= 9:f[i % 3] = f[(i - 1) % 3]if 10 <= b <= 26:f[i % 3] += f[(i - 2) % 3]return f[n % 3]
复杂度分析
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)
这篇关于算法第十三天-解码方法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!