0639. Decode Ways II

题目信息

题号:

0639

难度:

Hard

主题:

编码字符串、通配符、单字符与双字符解码、方案计数

原题:

LeetCode 0639

重点:

1 到 26 分别映射 A 到 Z、星号只能代表 1 到 9、零不能单独解码、统计所有通配符取值和分组方式

题目重述

字母 A 到 Z 分别由数字 1 到 26 编码。给定字符串 s,其中字符可以是十进制数字或 '*';每个 '*' 独立代表 1 到 9 中的任意一个数字。返回 s 能够解码成字母字符串的方案数量。

每次可以使用一个字符形成 1..9 的编码,或使用相邻两个字符形成 10..26 的编码;字符 '0' 不能单独解码。不同的星号取值或不同的合法分组都属于不同方案。s.length 位于 [1, 10^5],答案对 10^9 + 7 取模。

自建示例

星号与零必须组成两位编码:

输入:s = "*0"
输出:2
解释:星号只能取 1 或 2,分别形成 10 和 20;零不能单独解码,因此只有两种方案。

星号不能与前面的 3 组成有效两位数:

输入:s = "3*"
输出:9
解释:星号可取 1 到 9,并分别作为单字符解码;31 到 39 都超过 26,不能作为两位编码。