MENU

Leetcode91. Decode Ways(动态规划)

2019 年 03 月 31 日 • 阅读: 1598 • LeetCode阅读设置

Leetcode91. Decode Ways(动态规划)

  • Medium
  • Accepted:245,933
  • Submissions:1,116,585

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

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

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

链接

https://leetcode.com/problems/decode-ways

题意

一段包含大写字母(A到Z)的消息通过映射可编码为数字,A到Z对应1到26,问:给定一个只包含数字的非空字符串,有多少种解码方式(即将数字用字母表示)。

题解

显而易见,将数字解码为对应的字母只能为1到26之间的数字,所以我们每次考虑将一位数(1~9,0除外)和两位数(10~26)编码为对应字母。

比如对于字符串112213,我们可以进行如下“分解”,解码一位后为12213,解码两位后为2233,然后接着对12213和2233解码,可以发现,出现了很多重复项,这就涉及到了重叠子结构

                        112213

              12213                    2213

        2213        213           213            13

     213    13      13   3     13   3        3  ""

  13   3  3  ""  3  ""      3  ""
   
 3  ""

对于这种情况,我们可以通过自顶向下的递归(记忆化搜索)或者自底向上的动态规划解决。

我们使用dp[n]表示长度为n的字符串的解码方式,dp数组初始化为0,其中dp[0]表示空字符串其值为1,dp[1]表示长度为1的字符串,不为0时其值为1。

$dp[i] = dp[i] + dp[i - 1] \ , \ s[i-1] \in [1, 9]$

$dp[i] = dp[i] + dp[i - 2] \ , \ s[i-2,i-1] \in [10, 26]$

事实上我们只用到了dp[i - 1]和dp[i-2],和“斐波那契数列”与“爬楼梯”类似,我们只需要使用两个变量来记录前面的值就行,没必要再开一个数组。

时间复杂度$O(n)$,空间复杂度$O(n)$和$O(1)$两种。

代码

  • Runtime: 8 ms, faster than 35.43% of C++ online submissions for Decode Ways.
  • Memory Usage: 8.6 MB, less than 20.00% of C++ online submissions for Decode Ways.
class Solution {
public:
    int numDecodings(string s) {
        int n = s.length();
        vector<int> dp(n + 1, 0);
        dp[0] = 1, dp[1] = (s[0] == '0') ? 0 : 1;
        for (int i = 2; i <= n; ++i)
        {
            if (s[i - 1] != '0')
                dp[i] += dp[i - 1];
            if (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))
                dp[i] += dp[i - 2];
        }
        return dp[n];
    }
};

// O(1) space

class Solution {
public:
    int numDecodings(string s) {
        int n = s.length();
        int prev1 = 1, prev2 = (s[0] == '0') ? 0 : 1;
        int ans = prev2;
        for (int i = 2; i <= n; ++i)
        {
            ans = 0;
            if (s[i - 1] != '0')
                ans += prev2;
            if (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))
                ans += prev1;
            prev1 = prev2;
            prev2 = ans;
        }
        return ans;
    }
};

参考


The end.
2019年3月31日 星期日