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日星期日