13. Dcode Message

This problem was asked by Facebook.

Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded.

For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'.

You can assume that the messages are decodable. For example, '001' is not allowed.

分析情況

• If string starts with zero, then there's no valid encoding.

• If the string's length is less than or equal to 1, there is only 1 encoding.

• If the first two digits form a number k that is less than or equal to 26, we can recursively count the number of encodings assuming we pick k as a letter.

• We can also pick the first digit as a letter and count the number of encodings with this assumption.

def decodeWays(msg):
  return r_decodeWays(msg, 0)

def r_decodeWays(msg, count):
    # 考慮msg長度=3的情況
    if len(msg) == 3:
        count = 0
        addCount = True
        # 1. 每個char都不能為0
        for c in msg:
            if int(c) == 0:
                addCount = False
        if addCount: count += 1

        # 2. 將長度切成2,1
        a = int(msg[0:2])
        b = int(msg[2:])
        if a >= 10 and a <= 26 and b > 0:
            count += 1

         # 3. 將長度切成1,2
        a = int(msg[0:1])
        b = int(msg[1:])
        if a > 0 and b >= 10 and b <= 26:
            count += 1

        return count

    else:
        return r_decodeWays(msg[:3], count) + r_decodeWays(msg[3:], count)

Time: O(2^n)

[初學者學演算法｜從費氏數列認識何謂遞迴](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E5%BE%9E%E8%B2%BB%E6%B0%8F%E6%95%B8%E5%88%97%E8%AA%8D%E8%AD%98%E4%BD%95%E8%AC%82%E9%81%9E%E8%BF%B4-dea15d2808a3)

TODO: 遞迴算法的時間分析