0639. Decode Ways II¶
题目信息¶
- 题号:
0639
- 难度:
Hard
- 主题:
编码字符串、通配符、单字符与双字符解码、方案计数
- 原题:
- 重点:
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,不能作为两位编码。