劍指offer：把數(shù)字翻譯成字符串

題目要求：
給定一個數(shù)字，按照如下規(guī)則翻譯成字符串：0翻譯成“a”，1翻譯成“b”...25翻譯成“z”。一個數(shù)字有多種翻譯可能，例如12258一共有5種，分別是bccfi，bwfi，bczi，mcfi，mzi。實現(xiàn)一個函數(shù)，用來計算一個數(shù)字有多少種不同的翻譯方法。

# -*- coding: utf-8 -*-
# @Time         : 2019-07-10 21:13
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : getTranslationCount.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

def getTranslationCount(number):
    """
    要將一個數(shù)字轉化成一個字符串，由于這個數(shù)字有很多位，我們最直觀的就是從頭開始，一位一位地去轉化。
    比如給定12258. 我們可以先把1翻譯成b，然后剩下2258；也可以先把12翻譯成m，然后剩下258.。。

    由此可見是一個遞歸問題，用遞歸的思路分析題目，用循環(huán)來解決問題(動態(tài)規(guī)劃)
    遞推公式為：f(i) = f(i+1) + g(i, i+1) x f(i+2)

    其中f(i)表示到下標為i的數(shù)字為止，共有多少種可能的翻譯。之所以寫成向前遞推的公式，是因為如果我
    們從前往后翻譯，會出現(xiàn)很多重復的子問題，比如12258=1 | 2258，其中2258=2 | 258，而12258=12 | 258，
    這樣258就重復了。
    所以我們從后往前翻譯，就可以避免這樣的重復子問題。
    """
    def helper(s):
        # 一個數(shù)字至少有一種翻譯，因此可以先設置一個全為1的數(shù)組，長度對應數(shù)字的位數(shù)加一
        counts = [1] * (len(s) + 1)
        # 對于前面的n-1位
        for i in range(len(s) - 2, -1, -1):
            # 第i位至少有和第i+1位一樣多的翻譯數(shù)
            count = counts[i + 1]
            # 如果第i位和第i+1位可以組合成一個10-25的數(shù)字，那么g(i, i+1) = 1
            # f(i) = f(i+1) + g(i, i+1) x f(i+2)
            # 由于我們設置的數(shù)組長度是位數(shù)+1，因此這里i+2不可能越界
            if 10 <= int(s[i: i + 2]) <= 25:
                count += counts[i + 2]
            counts[i] = count
        return counts[0]

    # 由于0對應a，25對應z，因此小于0的輸入是無效的
    if number < 0:
        return 0

    return helper(str(number))