算法题--计算字符串的解码方式数

image.png

0. 链接

题目链接

1. 题目

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

2. 思路1：动态规划

• 字符串！算极值！果断想到动态规划
• 先考虑以下例子:

1    -> 结果 1(1)
11   -> 结果 2(1 1 和 11)
01   -> 结果 0 说明不能以0开头
100  -> 结果 0 说明0前面不能出现0
30   -> 结果 0 说明0前面不能出现非1非2的其他数
22   -> 结果 2(2 2 和 22)
226  -> 结果 3(2 2 6 和 22 6 和 2 26)

明显结果答案跟数字位数是直接相关的
计 dp[n] = 对前n位数字的解码方式

根据上面的最后两个例子, 可以粗略得出，n = 3时的结果，是在n=2的结果的基础上得出的，具体来说，6有2种选择:

1. 跟前面1位的2结合
2. 自己独立成码

当第1种情况发生时, 意味着解码方式跟26左边的数字的解码方式是想同的，因为26已经确定要结合并追加在左边数字后面了, 即dp[n - 2]

当第2种情况发生时, 意味着解码方式跟6左边的数字的解码方式是相同的，因为6已经确定要追加在左边数字后面了，即 dp[n - 1]

粗略看来，6只有这两种可能选择, 所以 dp[n] = dp[n - 1] + dp[n - 2]

于是，动态规划的三要素可以写出了:

• 重叠子问题: 求dp[n]的时候，需要求dp[i<n]的值, 最终需要求dp[1]的值; 而求dp[n-1]的时候, 也需要求dp[i < n - 1]的值，最终也需要求dp[1]的值, 可见dp[1]是重叠子问题, 同理 dp[2], dp[3], ..., dp[n - 2]都是重叠的子问题
• 最优子结构: 已知 dp[n - 1] 和 dp[n - 2]即可求出 dp[n], 所以对于dp[n]而言，省去了继续往左探索的需要，且求 dp[n] 的时候，不会影响已经求出的 dp[n - 1] 和 dp[n - 2]的值，满足最优子结构要求
• 状态转移方程: dp[n] = dp[n - 1] + dp[n - 2]

前面写的这么爽，是否问题就结束了呢？

并没有，可以这么写，是有前提条件的，就是一些边界问题。
意外情况:

• 若字符串为空或者头部为0, 则整个字符串无法解码
• 若 s[n - 1] 为0的话, s[n - 2]的值非1非2，那么，就没有合法的s[n - 2]来照顾s[n - 1]的0， 这就出现了非法值，导致整个字符串解码失败
• 若s[n - 1]=0 且 s[n - 2]为1或2, 此时, s[n - 1]只能跟s[n - 2]结合，而不能独立成码, 此时就少了一种可能性, dp[n] = dp[n - 2]
• 若 s[n - 1]取值为7~9, 而s[n - 2]非1非2, 意味着 s[n - 1] 不能跟 s[n - 2] 结合, 必须独立成码, 此时就少了一种可能性, dp[n] = dp[n - 1], 而非dp[n] = dp[n - 1]了

最后，初始值
定义dp = [0] * (n + 1)
dp[0] = dp[1] = 1

dp[0]是来凑数的，为了dp[2] = dp[1] + dp[0]成立
dp[i]表示从左到右第i个字符

3. 代码

# coding:utf8


class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0
        if n == 1:
            return 0 if s == '0' else 1
        if s[0] == '0':
            return 0

        dp = [0] * (len(s) + 1)
        dp[0] = 1
        dp[1] = 1
        for i in range(1, len(s)):
            if s[i] == '0':
                if s[i - 1] != '1' and s[i - 1] != '2':
                    return 0
                dp[i + 1] = dp[i - 1]
            elif s[i - 1] == '1' or (s[i - 1] == '2' and '1' <= s[i] <= '6'):
                dp[i + 1] = dp[i] + dp[i - 1]
            else:
                dp[i + 1] = dp[i]

        return dp[n]


def my_test(solution, s):
    print('input: s="{}", output: {}'.format(s, solution.numDecodings(s)))


solution = Solution()
my_test(solution, '')
my_test(solution, '0')
my_test(solution, '00')
my_test(solution, '230')
my_test(solution, '1')
my_test(solution, '12')
my_test(solution, '36')
my_test(solution, '202')
my_test(solution, '226')
my_test(solution, '2212')
my_test(solution, '110')

输出结果

input: s="", output: 0
input: s="0", output: 0
input: s="00", output: 0
input: s="230", output: 0
input: s="1", output: 1
input: s="12", output: 2
input: s="36", output: 1
input: s="202", output: 1
input: s="226", output: 3
input: s="2212", output: 5
input: s="110", output: 1

4. 结果

image.png