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.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

A: 一维动态规划

    int numDecodings(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(s.empty()||s[0]=='0')
            return 0;
        vector<int> dp(s.size()+1);
        
        dp[0] = 1;
        dp[1] = 1;
        for(int i=2;i<=s.size();i++)
        {
            if(s[i-1]=='0')
            {
                if(s[i-2]<='2'&&s[i-2]>'0')
                    dp[i] = dp[i-2];   
                else
                    return 0;
            }else
            {                
                if(s[i-2]=='0'||s[i-2]>'2'||(s[i-2]=='2'&&s[i-1]>'6'))
                    dp[i] = dp[i-1];
                else
                    dp[i] = dp[i-1]+dp[i-2];            
            }

        }
        
        return dp[s.size()];
    }

　　更简洁的作法：

    int numDecodings(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(s.empty())
            return 0;
        int n = s.size();
        vector<int> dp(n+1);
        
        dp[0] = 1;
        for(int i=1;i<=n;i++)
        {
            int c1=0,c2=0; //分别考虑dp[i-1]和dp[i-2]
            if(s[i-1]!='0')
                c1 = dp[i-1];
            if(i>=2&&(s[i-2]=='1'||s[i-2]=='2'&&s[i-1]<='6'))
                c2 = dp[i-2];
            dp[i] = c1+c2;
        }
        
        return dp[n];
        
    }

原文链接: https://www.cnblogs.com/summer-zhou/p/3324281.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/104668

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

Decode Ways

相关推荐