题目
一条包含字母 A-Z 的消息通过以下方式进行了编码:
1
2
3
4 'A' -> 1
'B' -> 2
...
'Z' -> 26给定一个只包含数字的非空字符串,请计算解码方法的总数。
示例 1:
1
2
3 输入: "12"
输出: 2
解释: 它可以解码为 "AB"(1 2)或者 "L"(12)。示例 2:
1
2
3 输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/decode-ways
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
首先这是一道计算方法总数的题目,回溯一定可以解决问题,对于每一个数字,都可以单独解码或者结合下个数字一起解码,如果使用哈希表,那么每次解码时间为$O(1)$,遍历所有情况需要$O(2^N)$的时间复杂度。
确定 base case:只有一个数字时,解码方法只有一种,有两个数字时,有两种。这其实是一道青蛙跳台阶,加上了额外的限定条件;
明确状态:数组长度;
明确选择:单独解码 or 结合下一个一起解码
动态规划数组含义:数组长度为 n 时,对应的解码方法。由于数字与字母一一对应不可能重复,因此不需要去重,只需要判断是否有效;
状态转移方程:
$$
dp[n] = dp[n-1] + dp[n-2],\ if\ nums[i]\times 10+nums[i+1]\ is\ valid
$$$$
dp[n] = dp[n-1],\ else
$$
代码如下:
1 | class Solution { |
通过这道题,明白了最难的其实也不是状态转移方程,而是特殊限制条件,需要考虑周全。为了考虑到所有特殊情况,最好办法是列举每一次选择时可能遇到的特殊值。
- 时间复杂度$O(N)$
- 空间复杂度$O(1)$