编码方式(dp)

LeetCode 91. Decode Ways 

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

描述:按照一下规则编码,给出一段由数字组成的字符串,判断可能得出的解码结果有多少种?

‘A‘ -> 1
‘B‘ -> 2
...
‘Z‘ -> 26
解析:类似于12,1既可以单独编码作为A,也可以和2一起作为L,所以可以想到是动态规划问题。那么久需要找出最优子问题。
假设dp(i)表示为第i个数开始的字符串能解码出的结果数,那么
dp(i)=dp(i+1),当第i个数单独编码时,
或dp(i)=dp(i+2),当第i个数和第i+1个数一起编码时。

这道题的通过率较低,主要原因就是有0这个边界条件。
当第i个数为0时,它无法单独编码,也无法和后面的数一起编码,因此此时dp[i]=0。
而只有第i个数为1或者第i个数为2且后面的数小于等于6时,才能一起编码。
另外,一旦字符串中出现了无法编码的情况,则整个字符串能解码的结果都为0。这些情况包括:1)首个字符为0;2)连续出现两个0;3)0前面出现的数大于2。我们可以先排除所有无法编码的情况,这可以减少计算量。
class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        if (!isValid(s)) return 0;
        int dp[n + 1];
        dp[n] = 1;
        dp[n - 1] = s[n - 1] != ‘0‘;
        for (int i = n - 2; i >= 0; --i) {
            if (s[i] == ‘0‘) dp[i] = 0;
            else if (s[i] == ‘1‘ || (s[i] == ‘2‘ && s[i + 1] <= ‘6‘)) dp[i] = dp[i + 1] + dp[i + 2];
            else dp[i] = dp[i+1];
        }
        return dp[0];
    }

    bool isValid(string &s) {
        if (s.empty() || s[0] == ‘0‘) return false;
        char pre = s[0], cur;
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == ‘0‘) {
                if (s[i - 1] == ‘0‘ || s[i - 1] > ‘2‘) return false;
            }
        }
        return true;
    }
};

由于动态规划是从后往前遍历,如果不先排除无法编码的情况,在首个字符为0等非法情况下依然需要遍历所有的字符串。当然,这不影响算法的思路。

相关文章