7. パターン数数え

問題

Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded. You can assume that the messages are decodable. For example, '001' is not allowed.

考え方

stringが与えられた時のデコード方法の数はstring[:-1]とstring[:-2]を用いて考えられる。 0 < string[-1:] < 10, 9 < string[:-2] < 27ならf(string) = f(string[:-1]) + f(string[:-2])と書けるので再帰的に行う。 stringが１文字と２文字の時は少し注意する。1~26までの数字しかdecodeできないので、それを条件に入れる。

計算量

２回分岐を繰り返すので、時間計算量はになる。 memoにキャッシュすれば計算量は減る。になる。

コード例

少し見栄えは悪いです。

def countWay(string):
    if len(string) == 1 and int(string) > 0:
        return 1
    if  len(string) == 2 and int(string) < 27:
        return 1 + countWay(string[:-1])

    if int(string[-1:]) > 0 and (int(string[-2:]) > 9 and int(string[-2:]) < 27):
        return countWay(string[:-1]) + countWay(string[:-2])
    elif int(string[-1:]) > 0:
        return countWay(string[:-1])
    elif  int(string[-2:]) > 9 and int(string[-2:]) < 27:
        return countWay(string[:-2])

if __name__ == "__main__":
    string = "111"
    print(countWay(string))