leetcode:Decode Ways

leetcode:Decode Ways

一、 題目

給定一個字符串包含26個字母，字母與數字產生映射，如：

‘A’ --> 1

‘B’ --> 2

…

‘Z’ --> 26

如果給一串數字，請給出編碼的方式有多少？

*注意：’12’ 可以編碼成”AB”,也可以編碼成”L”.

二、 分析

可以看出題目的目的是考察動態規劃，即每走一步可能有兩種情況，是不是和爬台階很像呢？對的。

這道題思路有兩種但是思路是一樣的：

1、 從前往後遍歷

(1)、ans[0] = 1;

(2)、如果s[0] = ‘0’，ans[1] = 0；否則ans[1] = 1;

(3)、遍歷判斷s[i-1]是否等於’0’，為0則ans[i] = 0;否則等於ans[i-1]，再判斷與後面一位組成的數是否大於26，小於則ans[i]= ans[i] + ans[i-2]

2、 從後往前遍歷

(1)、ans[len] = 1;

(2)、如果s[len-1] = ‘0’，ans[len-1] = 0；否則ans[len-1]= 1;

(3)、遍歷判斷s[i]是否等於’0’，為0則continue;否則判斷與後面一位組成的數是否大於26，大於則ans[i] = ans[i+1]，否則ans[i] = ans[i+1] + ans[i+2]

1、正序遍歷法：

class Solution {
public:
    int numDecodings(string s) {
        int len = s.size();
        if(len == 0) return 0;
        int ans[len+1];
        ans[0] =1;
        if(s[0] != '0')
        	ans[1] = 1;
        else ans[1] = 0;

        for(int i=2;i<=len;i++){
        	if(s[i-1] != '0')
        		ans[i] = ans[i-1];
        	else ans[i] = 0;
        	if(s[i-2] == '1'||(s[i-2] == '2' && s[i-1] <= '6'))
        		ans[i] = ans[i] + ans[i-2];
        }
        return ans[len]; 
    }
};

class Solution {
public:
    int numDecodings(string s) {
        int len = s.size();
        if(len == 0) return 0;
        int ans[len+1];
        memset(ans,0,len*sizeof(int));
        ans[len] =1;
        if(s[len-1] != '0')
        	ans[len-1] = 1;
        else ans[len-1] = 0;

        for(int i=len-2;i>=0;i--){
        	if(s[i] == '0')
        		continue;
        	if(s[i] > '2'||(s[i] == '2' && s[i+1] > '6'))
        		ans[i] = ans[i+1];
        	else ans[i] = ans[i+1] + ans[i+2];
        }
        return ans[0]; 
    }
};