LeetCode 91 Decode Ways

题目描述

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

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example, Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).

The number of ways decoding “12” is 2.

一句话题意

将字母A-Z按照1-26的顺序依次编号。

给定一个字符串,其只包含按照上面的规则编码之后的数字。求一共可以有多少种解码方式?

eg. “12”可以被解码成“AB”或者“L”,这样就是有2种方式。)

解题思路

一开始想到暴力搜索,但是对于“111111……”这样的数据来说,搜索是显然会超时的,所以用动规DP,避免重复计算,或者用记忆化搜索。

设定状态为:f[i]表示s0开始,长度为i的子串的解码方式数量,于是我们最终要求的答案便是f[n]

求解f[i]时,枚举最后一个字母对应1位还是2位,将f转化为求f[i-1]或者f[i-2]。

  • f[i] = 0
  • 枚举最后一个字母对应1位(要求s[i - 1] != '0'),那么有f[i] += f[i-1]
  • 枚举最后一个字母对应2位(要求i > 1s[i - 2]s[i - 1]组成的字符串在"10"~"26"的范围内),那么有f[i] += f[i - 2]

可以通过f[i – 1]和f[i – 2]计算出f[i]来,这就是我们的状态和转移方程。

在具体实现中,我们可以按照i从1到n的顺序,依次计算出所有的f[i]。

最后注意边界条件,特判s长度为0的情况,f[0]=1

提交AC~


0 条评论

发表评论