[LintCode] Decode Ways 解码方法

简介:

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

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.

Example
Given encoded message 12, it could be decoded as AB (1 2) or L (12).
The number of ways decoding 12 is 2.

LeetCode上的原题,请参见我之前的博客Decode Ways

解法一:

class Solution {
public:
    /**
     * @param s a string,  encoded message
     * @return an integer, the number of ways decoding
     */
    int numDecodings(string& s) {
        if (s.empty()) return 0;
        int n = s.size();
        vector<int> dp(n + 2, 1);
        for (int i = 2; i < n + 2; ++i) {
            if (s[i - 2] == '0') dp[i] = 0;
            else dp[i] = dp[i - 1];
            if (i >= 3 && (s[i - 3] == '1' || (s[i - 3] == '2' && s[i - 2] <= '6'))) {
                dp[i] += dp[i -2];
            }
        }
        return dp.back();
    }
};

解法二:

class Solution {
public:
    /**
     * @param s a string,  encoded message
     * @return an integer, the number of ways decoding
     */
    int numDecodings(string& s) {
        if (s.empty()) return 0;
        vector<int> dp(s.size() + 1, 0);
        dp[0] = 1;
        for (int i = 1; i < dp.size(); ++i) {
            if (s[i - 1] >= '1' && s[i - 1] <= '9') dp[i] += dp[i - 1];
            if (i >= 2 && s.substr(i - 2, 2) <= "26" && s.substr(i - 2, 2) >= "10") {
                dp[i] += dp[i - 2];
            }
        }
        return dp.back();
    }
};

解法三:

class Solution {
public:
    /**
     * @param s a string,  encoded message
     * @return an integer, the number of ways decoding
     */
    int numDecodings(string& s) {
        if (s.empty() || s.front() == '0') return 0;
        int c1 = 1, c2 = 1;
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == '0') c1 = 0;
            if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6')) {
                c1 = c1 + c2;
                c2 = c1 - c2;
            } else {
                c2 = c1;
            }
        }
        return c1;
    }
};

 本文转自博客园Grandyang的博客,原文链接:解码方法[LintCode] Decode Ways ,如需转载请自行联系原博主。

相关文章
|
8月前
Leetcode 6.ZigZag Conversion
如上所示,这就是26个小写字母表的5行曲折变换。 其中在做这道题的时候把不需要我们构造出这样五行字符,然后拼接。其实你把字母换成1-n的数字,很容易找到每个位置的字母在原字符串中的位置。
36 0
LeetCode 91. Decode Ways
字母A到Z分别和1到26的数字一一对应,给定一串用字符表示的数字,将数字串从不同位置拆开,每一个数字都对应一个字符,如此构成了一个字母字符串. 从不同的位置拆分数字字符串,可以得到不同的字母字符串,问一共有多少种有效的拆分方式.
54 0
LeetCode 91. Decode Ways
Leetcode-Easy 804. Unique Morse Code Words
Leetcode-Easy 804. Unique Morse Code Words
87 0
Leetcode-Easy 804. Unique Morse Code Words
LeetCode---Problem6 ZigZag Conversion
ZigZag问题思路。代码整洁并不一定执行速度就好~
775 0
|
机器学习/深度学习 Perl
LeetCode 91 Decode Ways(编码方式)(*)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/51340198 ...
957 0
LeetCode 92 Decode Ways
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/51339103 ...
672 0