KK's blog

每天积累多一些

0%

LeetCode 091 Decode Ways

Posted on Disqus:

LeetCode



A message containing letters from A-Z can be encoded into numbers using the following mapping:

‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”


To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

"AAJF" with the grouping (1 1 10 6) "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

Input: s = “12”
Output: 2
Explanation: “12” could be decoded as “AB” (1 2) or “L” (12).


Example 2:

Input: s = “226”
Output: 3
Explanation: “226” could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6).


Example 3:

Input: s = “06”
Output: 0
Explanation: “06” cannot be mapped to “F” because of the leading zero (“6” is different from “06”).


Constraints:

1 <= s.length <= 100 s contains only digits and may contain leading zero(s).

题目大意：

数字1-26可以解码成A-Z字母。给定一串数字，求解码方法数。

解题思路：

求种数是DP和DFS，这题有递归关系，所以考虑用DP。类似于Fibonacci数列和LeetCode 070 Climbing Stairs，但此题带限制条件

递归式：

1
dp[i] = dp[i-1] + dp[i-2] if 0 < s[i-1] <= 9, 10 <= s[i-2:i] <= 26

解题步骤：

利用DP五点注意事项

注意事项：

  1. 不合法的情况为空字符和含0. 这是求个数，根据DP知识点(数值到个数DP模板)，dp[0] = 1, 但这与题目空字符要求不同，所以特别处理。至于单个含0在循环中处理’0’ < s[i - 1] <= ‘9’
  2. 验证单位范围[1, 9], 双位范围[10, 26]才加入到结果中。由于dp长度只多了一位而递归式含两个前状态，所以要验证i >= 2

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
# dp[i] = dp[i-1] + dp[i-2] if 0 < s[i-1] <= 9, 10 <= s[i-2:i] <= 26
def numDecodings(self, s: str) -> int:
	if not s:
		return 0
	dp = [0] * (len(s) + 1)
	dp[0] = 1
	for i in range(1, len(dp)):
		if '0' < s[i - 1] <= '9':
			dp[i] = dp[i - 1]
		if i >= 2 and '10' <= s[i - 2: i] <= '26':
			dp[i] += dp[i - 2]
	return dp[-1]

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

O(1)空间算法II解题思路：

类似于Fibonacci数列和LeetCode 070 Climbing Stairs，由于涉及到两个前状态，所以用两个变量来节省空间

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
# dp[i] = dp[i-1] + dp[i-2] if 0 < s[i-1] <= 9, 10 <= s[i-2:i] <= 26
def numDecodings2(self, s: str) -> int:
	if not s:
		return 0
	first, second = 1, 1
	for i in range(1, len(s) + 1):
		res = 0
		if '0' < s[i - 1] <= '9':
			res = second
		if i >= 2 and '10' <= s[i - 2: i] <= '26':
			res += first
		first, second = second, res
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

Free mock interview