作者：翟天保Steven
版權(quán)聲明：著作權(quán)歸作者所有，商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處

題目描述：

有一種將字母編碼成數(shù)字的方式：'a'->1, 'b->2', ... , 'z->26'。

現(xiàn)在給一串數(shù)字，返回有多少種可能的譯碼結(jié)果

數(shù)據(jù)范圍：字符串長度滿足 0<n≤90

進階：空間復雜度 O(n)，時間復雜度O(n)

示例1：

輸入：

"12"

返回值：

2

說明：

2種可能的譯碼結(jié)果（”ab” 或”l”）

示例2：

輸入：

"31717126241541717"

返回值：

192

說明：

192種可能的譯碼結(jié)果

解題思路：

本題是動態(tài)規(guī)劃的經(jīng)典題目。有兩個解題思路，動態(tài)規(guī)劃和動態(tài)規(guī)劃進階(空間復雜度低)。

本題難點在于0的情況，10和20則只代表1種結(jié)果，11-19或21-26能代表2種結(jié)果，0不代表任何情況且可能會導致解碼失敗，1-9代表1種結(jié)果。

思路一：動態(tài)規(guī)劃

1. 用長度比字符串長度多1的dp存儲結(jié)果數(shù)。dp[0]初始化為1；i從1開始，dp[i]存放的是前i個數(shù)字可能的結(jié)果，所以dp[1]也為1，dp[2]開始就要分情況了。
2. 若i-1為0，則i-2必須為1或2，編碼才可能成功，10和20有字母，30及之后都沒有對應(yīng)字母了。那么有dp[i]等于dp[i-2]，相當于dp[i]在dp[i-2]種可能的基礎(chǔ)上多了一個雙數(shù)字字母，多一個字母則結(jié)果數(shù)是一致的。
3. 若i-2和i-1的位置能組合出11-19/21-26的數(shù)，則dp[i]相當于dp[i-1]和dp[i-2]之和。dp[i-1]表示截止到前i-1個數(shù)字可能的結(jié)果數(shù)，加上一個單數(shù)字對應(yīng)的字母，是一類情況；dp[i-2]表示截止到前i-2個數(shù)字可能的結(jié)果數(shù)，加上一個雙數(shù)字對應(yīng)的字母，是一類情況。
4. 若組合不出雙數(shù)字字母，那就只能是單數(shù)字字母了，所以dp[i]等于dp[i-1]。相當于dp[i]在dp[i-1]種可能的基礎(chǔ)上多了一個字母，多一個字母則結(jié)果數(shù)是一致的。
5. 最后返回dp[size]，size是字符串長度，就是size個字符可能的結(jié)果數(shù)。

思路二：動態(tài)規(guī)劃進階

? ? ? ?思路和思路一中基本一致。區(qū)別在于用pre和cur兩個int數(shù)動態(tài)刷新，來實現(xiàn)動態(tài)規(guī)劃，好處是空間復雜度降低，壞處是丟失了前面的結(jié)果數(shù)據(jù)只保留了最終結(jié)果。

? ? ? ?建議看懂思路一代碼再看思路二代碼。

測試代碼：

思路一：動態(tài)規(guī)劃

class Solution {
public:
    // 解碼
    int solve(string nums) {
        // 排除開頭為0的情況
        if(nums[0] == '0')
            return 0;
        // 動態(tài)規(guī)劃
        // dp[0]初始化為1；i從1開始，dp[i]存放的是前i個數(shù)字可能的結(jié)果，所以dp[1]也為1，dp[2]開始就要分情況了
        vector<int> dp(nums.size()+1, 1);
        for(int i = 2; i <= nums.size(); ++i){
            // 注意字符串下標是從0開始
            // 若i-1為0，則當i-2為1或2時，編碼才可能成功，10和20有字母，30及之后都沒有對應(yīng)字母了
            if(nums[i - 1] == '0'){
                // 若是10或20，則dp[i]等于dp[i-2]，相當于dp[i]在dp[i-2]種可能的基礎(chǔ)上多了一個字母，多一個字母則結(jié)果數(shù)是一致的
                if(nums[i - 2] == '1' || nums[i - 2] == '2')
                    dp[i] = dp[i - 2];
                else 
                    return 0;
            }
            // 若i-2和i-1的位置能組合出11-19/21-26的數(shù)，則dp[i]相當于dp[i-1]和dp[i-2]之和
            // dp[i-1]表示前i-1個數(shù)字可能的結(jié)果數(shù)，加上一個單數(shù)字對應(yīng)的字母，是一類情況
            // dp[i-2]表示前i-2個數(shù)字可能的結(jié)果數(shù)，加上一個雙數(shù)字對應(yīng)的字母，是一類情況
            else if(nums[i - 2] == '1' || (nums[i - 2] == '2' && nums[i - 1] > '0' && nums[i - 1] < '7')){
                dp[i] = dp[i - 1] + dp[i - 2];
            }
            // 若組合不出雙數(shù)字字母，那就只能是單數(shù)字字母了，所以dp[i]等于dp[i-1]
            // 相當于dp[i]在dp[i-1]種可能的基礎(chǔ)上多了一個字母，多一個字母則結(jié)果數(shù)是一致的
            else{
                dp[i] = dp[i - 1];
            }
        }
        return dp[nums.size()];
    }
};

思路二：動態(tài)規(guī)劃進階文章來源地址http://www.zghlxwxcb.cn/news/detail-465072.html

class Solution {
public:
    // 解碼
    int solve(string nums) {
        // 排除開頭為0的情況
        if(nums[0] == '0')
            return 0;
        // 動態(tài)規(guī)劃
        // 用pre表示前i-1個字符的可能數(shù)，cur表示前i個字符的可能數(shù)
        vector<int> dp(nums.size()+1, 1);
        int pre = 1;
        int cur = 1;
        for(int i = 2; i <= nums.size(); ++i){
            // temp存儲cur，因為cur馬上要被覆蓋了
            int temp = cur;
            // 注意字符串下標是從0開始
            // 若i-1為0，則當i-2為1或2時，編碼才可能成功，10和20有字母，30及之后都沒有對應(yīng)字母了
            if(nums[i - 1] == '0'){
                // 若是10或20，則cur等于上一輪的pre，也就是比當前位置靠前2步的數(shù)值
                if(nums[i - 2] == '1' || nums[i - 2] == '2')
                    cur = pre;
                else 
                    return 0;
            }
            // 若i-2和i-1的位置能組合出11-19/21-26的數(shù)，則cur等于上一輪的cur和pre之和
            // 上一輪的cur表示前i-1個數(shù)字可能的結(jié)果數(shù)，加上一個單數(shù)字對應(yīng)的字母，是一類情況
            // 上一輪的pre表示前i-2個數(shù)字可能的結(jié)果數(shù)，加上一個雙數(shù)字對應(yīng)的字母，是一類情況
            else if(nums[i - 2] == '1' || (nums[i - 2] == '2' && nums[i - 1] > '0' && nums[i - 1] < '7')){
                cur = cur + pre;
            }
            // 若組合不出雙數(shù)字字母，那就只能是單數(shù)字字母了，所以cur相比上一輪的cur無數(shù)值變化，這段代碼也可以刪除，為了便于分情況理解我加上了
            else{
                cur = cur;
            }
            // 這一輪的pre等于上一輪的cur
            pre = temp;
        }
        return cur;
    }
};

到了這里，關(guān)于劍指offer(C++)-JZ46：把數(shù)字翻譯成字符串(算法-動態(tài)規(guī)劃)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！