题目

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.

分析

我采用的是动态规划，依次寻找可能的解码方法。如果出现无法解码的，需要返回0。

int Decodings(char *s,int n)
{
    int ans=0;
    if(s[n]=='\0')
        return 1;
    if(s[n]>='1'&&s[n]<='9')
        ans=ans+Decodings(s,n+1);
    if(s[n]=='1'&&s[n+1]!='\0'&&s[n+1]>='0'&&s[n]<='9')
        ans=ans+Decodings(s,n+2);
    if(s[n]=='2'&&s[n+1]!='\0'&&s[n+1]>='0'&&s[n+1]<='6')
        ans=ans+Decodings(s,n+2);
    return ans;
}

int numDecodings(char* s) {
    int ans=0;
    if(s[0]=='\0')
        return 0;
    ans=Decodings(s,0);
    return ans;
}

上面的递归的方法，运行时间较长，可以改为数组来保存，a[n]=a[n-1]+a[n-2];

int Decodings(char *s,int n)
{
    int ans=0;
    if(s[n]=='\0')
        return 1;
    if(s[n]>='1'&&s[n]<='9')
        ans=ans+Decodings(s,n+1);
    if(s[n]=='1'&&s[n+1]!='\0'&&s[n+1]>='0'&&s[n]<='9')
        ans=ans+Decodings(s,n+2);
    if(s[n]=='2'&&s[n+1]!='\0'&&s[n+1]>='0'&&s[n+1]<='6')
        ans=ans+Decodings(s,n+2);
    return ans;
}

int numDecodings(char* s) {
    int ans=0;
    if(s[0]=='\0')
        return 0;
    //ans=Decodings(s,0);
    int n=0;
    while(s[n]!='\0')
        n++;
    int *a=(int *)malloc(sizeof(int)*(n+1));
    a[0]=0;a[1]=0;
    if(s[0]>='1'&&s[0]<='9')
        a[0]=1;
    else
        return 0;
    if(s[1]!='\0'&&s[1]>='1'&&s[1]<='9')
        a[1]+=1;
    if((s[0]=='1'&&s[1]>='0'&&s[1]<='9')||(s[0]=='2'&&s[1]>='0'&&s[1]<='6'))
        a[1]+=1;
    for(int i=2;i<n;i++)
    {
        a[i]=0;
        if(s[i]>='1'&&s[i]<='9')
            a[i]+=a[i-1];
        if((s[i-1]=='1'&&s[i]>='0'&&s[i]<='9')||(s[i-1]=='2'&&s[i]>='0'&&s[i]<='6'))
            a[i]+=a[i-2];
    }
    //printf("%d %d\n",ans,a[n-1]);
    return a[n-1];
}