算法第十三天-解码方法

解码方法

题目要求

解题思路

来自【宫水三叶】

基本分析

我们称一个解码内容为一个item。
根据题意，每个item可以由一个数字组成，也可以由两个数字组成。
数据范围为100，很具有迷惑性，可能会有不少同学会想使用DFS进行暴力搜索。
我们可以大致分析一下这样子的做法是否可行：不失为一般性的考虑字符串s中的任意位置i，位置i既可以作为一个独立item，也可以与上一位置组成新item，那么相当于每个位置都有两种分割选择（先不考虑分割结果的合法性问题），这样子做法的复杂度是$O(2^n)$的，当n范围是100时，远超我们计算机单秒运算量$(10^7)$。及时我们将[判断分割结果是否合法]的操作放到暴力搜索过程中做剪枝，也与我们的单秒运算量相差很远。
递归的方法不可行，我们需要考虑递推的解法。

动态规划

这其实时一道字符串类的动态规划题，不难发现对于字符串s的某个位置i而言，我们只关心[位置i自己能否形成独立item]和[位置i能够与上一位置（i-1）能否形成item]，而不关心i-1之前的位置。

有了以上分析，我们可以从前往后处理字符串s，使用一个数组记录以字符串s的每一位作为结果的解码方案数。即定义$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]
  因此，我们有如下转移方程：
  $$?\begin{array}{r}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{array}$$
  其他细节：由于本题存在前导零，而前导零属于无效item。可以进行特判，但个人习惯往字符串头部追加空格作为哨兵，追加空格既可以避免讨论前导零，也能使下标从1开始，简化f[i-1]等负数下标的判断。

代码

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        s = ' ' + s
        f =[0] *(n+1)
        f[0]=1
        for 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)$

空间优化

不难发现，我们转移f[i]时只依赖f[i-1] 和 f[i-2]两个状态。因此我们可以采用与[滚动数组]类似的思路，只创建长度为3的数组，通过取余的方式来复用不再需要的下标。

代码

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        s = ' ' + s
        f = [0] * 3
        f[0] = 1
        for i in range(1,n + 1):
            f[i % 3] = 0
            a = 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(1)$