最新公告
  • 欢迎您光临信息学奥赛网,一个优质的信息学编程题库和信息学编程学习资源专业网站。欢迎加入VIP
  • 解码方法 II

    正文概述 陈老师   2026-01-20 15:30:29  

    题目描述

    给定一个字符串 s,该字符串由数字和 * 字符组成,该字符串中的数字根据给定的映射规则进行编码:

    • 1 到 9 分别映射到 'A' 到 'I'
    • 10 到 26 分别映射到 'J' 到 'Z'

    * 可以表示从 1 到 9 的任一数字(不包括 0)。要求解码该字符串,并返回解码方法的总数。注意,解码方法可能非常多,因此结果需要对 109+710^9 + 7 取模。

    输入格式

    输入为一个字符串 s,只包含数字和 * 字符。

    输出格式

    输出一个整数,表示解码方法的总数。

    样例

    *
    
    9
    
    1*
    
    18
    
    2*
    
    15
    

    提示

    样例1解释

    这一条编码消息可以表示 1 到 9 中的任意一个数字,因此可以解码成 A 到 I 中的任意一个字母,共有 9 种解码方法。

    样例2解释

    这一条编码消息可以表示 11、12、13、14、15、16、17、18 或 19 中的任意一条。 每种消息都可以由 2 种方法解码(例如,11 可以解码成 AA 或 K)。 因此,1* 共有 9 * 2 = 18 种解码方法。

    样例3解释

    这一条编码消息可以表示 21、22、23、24、25、26、27、28 或 29 中的任意一条。 21、22、23、24、25 和 26 由 2 种解码方法,但 27、28 和 29 仅有 1 种解码方法。 因此,2* 共有 (6 * 2) + (3 * 1) = 12 + 3 = 15 种解码方法。

    数据范围

    • 字符串 s 可能包含前导零。
    占比 数据范围
    10% 0<s.length≤100<s.length\le 10
    30% 10<s.length≤10010<s.length\le 100
    60% 100<s.length≤105100<s.length\le 10^5
    信息学奥赛网,一个优质的信息学奥赛学习资源平台!
    信息学奥赛网 » 解码方法 II