“给定一个只含数字的字符串,计算并返回解码方法的总和。”
题目链接:
来源:力扣(LeetCode)
链接:91. 解码方法 - 力扣(LeetCode) (leetcode-cn.com)
一条包含字母 A-Z 的消息通过以下映射进行了 编码 :
'A' -> "1" 'B' -> "2" ... 'Z' -> "26"
要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,"11106" 可以映射为:
给你一个只含数字的 非空 字符串 s ,请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。
示例 1:
输入: s = "12"
输出: 2
解释: 它可以解码为 "AB"(1 2)或者 "L"(12)。
示例 2:
输入: s = "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
这道题动态规划、递归都可以。
首先分析题意,对于给定的字符串s,对它进行解码,返回解码数量。
具体来说就是,对于字符串s,在解码的时候判断使用了s中的那些字符,会出现两种情况:
由此,可以写出状态转移方式,进行动态规划:
fi=fi−1,其中 s[i]/0 fi=fi−2,其中 s[i−1]≠0 ,并且 10*s[i−1]+s[i]≤26
代码参考:
class Solution {
public int numDecodings(String s) {
int n = s.length();
// a = f[i-2], b = f[i-1], c=f[i]
int a = 0, b = 1, c = 0;
for (int i = 1; i <= n; ++i) {
c = 0;
if (s.charAt(i - 1) != '0') {
c += b;
}
if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
c += a;
}
a = b;
b = c;
}
return c;
}
}
时间复杂度 : O(n)
其中n是字符串s的长度。
空间复杂度: O(n)
如果使用数组进行状态转移,空间复杂度为O(n),如果仅使用三个变量,空间复杂度为O(1)。
这道题首先要理解清楚解码规则。
找出动态规划方程,使用动态规划找出答案。