Участник:ArthurSamuelyan/Decode Ways II

Материал из DISCOPAL
Перейти к: навигация, поиск
class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
 
        mod = 1000000007
        decodeWays = []
 
        # Отдельно обработаем первый символ
        if s[0] == '0':
            return 0
 
        elif s[0] == '*':
            decodeWays.append(9)
 
        else:
            decodeWays.append(1)
 
        for i in range(1, len(s)):
            # Множитель, учитывающий -2 символ
            dWays2 = 1
            if i >= 2:
                dWays2 = decodeWays[i-2]
 
 
            if s[i] == '0':
                # Тогда кодировка имеет смысл
                # только если перед ним стоит (или можно поставить) '1' или '2'
 
                if s[i-1] == '1' or s[i-1] == '2':
                    decodeWays.append(dWays2)
 
                elif s[i-1] == '*':
                    decodeWays.append(dWays2 * 2)
 
                else:
                    return 0
 
 
            elif s[i] == '*':
                decodeWays.append(decodeWays[i-1] * 9)
                if s[i-1] == '*':
                    # 11 - 19 and 21 - 26
                    decodeWays[i] += dWays2 * 15
 
                elif s[i-1] == '1':
                    # 11 - 19
                    decodeWays[i] += dWays2 * 9
 
                elif s[i-1] == '2':
                    # 21 - 26
                    decodeWays[i] += dWays2 * 6
 
                # В остальных случаях эта * не может являться продолжением кодировки символа
 
 
            else:
                decodeWays.append(decodeWays[i-1])
                if s[i-1] == '*':
                    # Учитываем, что вместо * можно подставить 1
                    decodeWays[i] += dWays2
                    if s[i] in ['0', '1', '2', '3', '4', '5', '6']:
                        # Учитываем, что вместо * также можно подставить и 2
                        decodeWays[i] += dWays2
 
                else:
                    # Проверяем, что последние 2 символа железно заданы
                    if s[i-1] == '1':
                        decodeWays[i] += dWays2
 
                    elif s[i-1] == '2' and s[i] in ['0', '1', '2', '3', '4', '5', '6']:
                        decodeWays[i] += dWays2
 
 
            decodeWays[i] %= mod
 
        return decodeWays[-1]