C++ DP solution


  • 0
    2

    class Solution {
    public:
    int numDecodings(string s) { //使用动态规划求解,类似于斐波那契数列;
    int len=s.length();
    if(len==0 || s[0]=='0') return 0;
    int* record=new int[len];
    record[0]=1;
    int last=((int)s[0]-'0')*10+((int)s[1]-'0');
    if(s[1]=='0') record[1]= last>26?0:1;
    else record[1]= last>26?1:2;
    for(int i=2;i<len;i++)
    {
    last=((int)s[i-1]-'0')*10+((int)s[i]-'0');
    if(last<1) return 0;
    if(s[i]=='0')
    {
    if(last>26) return 0;
    record[i]=record[i-2];
    }
    else
    {
    if(s[i-1]!='0' && last<=26) record[i]=record[i-1]+record[i-2]; //fibo
    else record[i]=record[i-1];
    }
    }
    return record[len-1];
    }
    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.