解码方法

解码方法

要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,“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;
    }
};
上一篇:0015-leetcode算法实现之三数之和-3sum-python&golang实现


下一篇:15. 三数之和