解码方法

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，“11106” 可以映射为：
“AAJF” ，将消息分组为 (1 1 10 6)
“KJF” ，将消息分组为 (11 10 6)
题目链接

1.动态规划分析求解

class Solution {
public:
    int numDecodings(string s) {
        if(s.size()==0||s[0]=='0')
        return 0;

        //最少有一个元素，且第一个元素不为0
        vector<int> dp(s.size(),0);
        dp[0]=1;

        for(int i=1;i<s.size();i++)
        {
            if(s[i]=='0')//只能与前面进行组合
            {
                if(s[i-1]>'2'||s[i-1]=='0')//不能进行组合
                return 0;

                if(i>=2)
                dp[i]=dp[i-2];
                else
                dp[i]=1;//第二个元素为0
            }
            else//s[i]!=0
            {
                if(s[i-1]=='1')//前面为1，
                   {
                       if(i-2>=0)
                       dp[i]=dp[i-1]+dp[i-2];
                       else
                       dp[i]=2;//当前为第二个元素
                   }
                else if(s[i-1]=='2'&&s[i]<='6')//前面为2
                    {
                        if(i-2>=0)
                        dp[i]=dp[i-1]+dp[i-2];
                        else
                        dp[i]=2;
                    }
                else
                dp[i]=dp[i-1];
            }
        }
        return dp[s.size()-1];
    }
};

2.空间复杂度优化

上述代码之中，空间复杂度为O(N),由代码可知，dp[i]只与dp[i-1]和dp[i-2]有关系，因此可以定义三个变量来保存这三个值，使空间复杂度降为O(1)

class Solution {
public:
    int numDecodings(string s) {
        if(s.size()==0||s[0]=='0')
            return 0;
        //dp[i]=dp[i-1]+dp[i-2];
        int first=1;
        int second=1;
        int third=first;

        for(int i=1;i<s.size();i++)
        {
            if(s[i]=='0')
            {
                if(s[i-1]=='0'||s[i-1]>'2')
                    return 0;
                else
                {
                    third=second;
                    second=first;
                    first=third;
                }
            }
            else//s[i]!+'0'
            {
                if(s[i-1]=='1')
                {
                    third=first+second;
                    second=first;
                    first=third;
                }
                else if(s[i-1]=='2'&&s[i]<='6')
                {
                    third=first+second;
                    second=first;
                    first=third;
                }
                else
                    {
                    third=first;
                    second=first;
                    first=second;
                    }
            }
        }
        return third;
    }
};