Decode Ways

Q: Как обрабатывать нули в задаче Decode Ways?

0 никогда не является отдельной буквой, поэтому он должен сочетаться с предшествующей цифрой, образуя 10 или 20 . Он добавляет количество из двух цифр назад только после 1 или 2, а в остальных случаях — ничего. Начальный 0 , два нуля подряд или 0 после числа от 3 до 9 дают 0.

СреднеДинамическое программирование

+10

Сообщение, состоящее из заглавных букв, закодировали с помощью A = 1, B = 2 и так далее до Z = 26, а коды записали без разделителей. Для данной строки цифр s верните количество сообщений, из которых она могла получиться.

Буква считывается по одной цифре или двум соседним цифрам, а код никогда не начинается с 0: 06 — это не 6, а отдельный 0 не является буквой. Если ни один вариант прочтения не подходит, верните 0.

Функция

numDecodings(s: string) → integer

sstring: строка цифр для декодирования
Возвращаетinteger: количество буквенных сообщений, кодируемых в s

Ограничения

1 ≤ s.length ≤ 100
s содержит только цифры от 0 до 9, и может начинаться с 0.
У каждого префикса и каждого суффикса s меньше 2³¹ вариантов прочтения, поэтому ответ и все промежуточные подсчёты помещаются в знаковое 32-битное целое число.

Примеры

Ввод: s = "2611"
Вывод: 4
Пояснение: Четыре прочтения: 2 6 1 1 (BFAA), 26 1 1 (ZAA), 2 6 11 (BFK) и 26 11 (ZK). Средние цифры никогда не объединяются в пару, потому что 61 больше 26.

Ввод: s = "1203"
Вывод: 1
Пояснение: 0 должна сочетаться с предшествующей ей 2 как 20, что вынуждает выбрать 1 20 3 (ATC). Если сначала прочитать 12, 0 останется отдельно, а 03 начинается с 0.

Ввод: s = "06"
Вывод: 0
Пояснение: Первая буква должна начинаться с 0. Одиночный 0 — это не буква, а 06 — не код, поэтому ни одно сообщение не даст эту строку.

Дополнительный вопрос

Что, если s также может содержать *, обозначающую любую цифру от 1 до 9? Сможешь подсчитать количество вариантов прочтения за время O(n), по модулю 10^9+7?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Каждая цифра — это отдельная буква или она соединяется с соседней, поэтому количество вариантов чтения растёт как числа Фибоначчи: для 45 единиц существует 1836311903 варианта. Перечислить их все невозможно, но способы завершить чтение зависят только от достигнутой позиции, поэтому каждую позицию нужно учитывать один раз. 0 может завершать только 10 или 20.

Попробуйте оба прочтения с рекурсией

Верно, но не успевает на самых больших тестах

Идея

В позиции i цифра 0 не начинает ни одной буквы, поэтому этот путь не даёт вариантов прочтения. В противном случае прочитай одну цифру и подсчитай остальные, начиная с i+1; если две цифры образуют число от 10 до 26, прочитай также обе цифры и подсчитай варианты, начиная с i+2. Два варианта дают разные первые буквы, поэтому их количества складываются без пересечений, а достижение конца означает, что получен один вариант прочтения.

Ничего не запоминается, поэтому вызовы следуют правилу Фибоначчи: для 45 единиц требуется примерно 5 × 10^9 вызовов. Ответ 0 не ускоряет работу: 44 единицы, 55 троек и заключительный 0 требуют примерно 10^11 вызовов, поскольку каждый вариант прочтения единиц обрывается только на последней цифре.

Алгоритм

waysFrom(i) подсчитывает количество вариантов декодирования цифр начиная с индекса i.
В конце строки верните 1. Если встретился 0, верните 0.
В противном случае верните waysFrom(i+1), а также waysFrom(i+2), если цифры i и i+1 образуют число не больше 26.
Ответ — waysFrom(0).

def numDecodings(s):
    n = len(s)

    def ways_from(i):
        # The number of ways to decode s[i:].
        if i == n:
            return 1  # nothing left: one finished reading
        if s[i] == "0":
            return 0  # no letter code starts with 0
        ways = ways_from(i + 1)  # read one digit
        if i + 1 < n and int(s[i:i + 2]) <= 26:
            ways += ways_from(i + 2)  # read two digits, 10 to 26
        return ways

    return ways_from(0)

Рекурсия с мемоизацией

Идея

Рекурсия задаёт один и тот же вопрос много раз. В "11111" нужен подсчёт начиная с индекса 3 после 1 1 1, после 11 1 и после 1 11, и каждый раз он одинаковый, потому что зависит только от цифр начиная с индекса 3. Сохраняй каждый подсчёт при первом вычислении и помечай ещё не вычисленные ячейки значением -1, поскольку 0 — это настоящий результат подсчёта.

Есть n позиций, каждая вычисляется один раз за постоянное время: время O(n). Мемоизация и стек вызовов занимают O(n) памяти, глубина — не более 100 вызовов.

Алгоритм

Заполни memo значением -1, по одному слоту на каждый индекс.
В waysFrom(i) возвращай 1 в конце строки и memo[i], если оно не равно -1.
Иначе считай, как при обычной рекурсии, сохраняй результат в memo[i], включая ноль, и возвращай его.

def numDecodings(s):
    n = len(s)
    memo = [-1] * n  # memo[i]: ways to decode s[i:], -1 until worked out

    def ways_from(i):
        if i == n:
            return 1
        if memo[i] != -1:
            return memo[i]
        ways = 0
        if s[i] != "0":
            ways = ways_from(i + 1)  # read one digit
            if i + 1 < n and int(s[i:i + 2]) <= 26:
                ways += ways_from(i + 2)  # read two digits, 10 to 26
        memo[i] = ways
        return ways

    return ways_from(0)

Снизу вверх с двумя счётчиками

Идея

Вместо этого считайте префиксы. Пусть ways(i) — количество вариантов декодирования первых i цифр. Последняя буква может соответствовать только цифре i-1, для которой допустимы значения от 1 до 9; тогда остаётся ways(i-1) вариантов декодирования. Либо она может соответствовать цифрам i-2 и i-1 вместе: они должны образовывать число от 10 до 26, и тогда остаётся ways(i-2) вариантов. Складывайте слагаемые, условие для которых выполняется. У пустого префикса один вариант декодирования, поэтому ways(0) = 1.

Для "1203" количество вариантов сначала равно 1, затем 2, а на 0 снова становится равным 1, потому что подходит только 20, и оно оставляет количество вариантов, которое было перед 2. 3 декодируется отдельно, поэтому количество вариантов остаётся равным 1. Каждое значение зависит от двух предыдущих, поэтому вместо таблицы достаточно двух переменных: время O(n), память O(1).

Алгоритм

Установите twoBack = 0 и oneBack = 1 — количество способов для пустого префикса.
Для каждого индекса i установите current равным oneBack, если цифра i не равна 0, иначе — 0.
Если i ≥ 1, цифра i-1 не равна 0, а цифры i-1 и i вместе образуют число не больше 26, прибавьте twoBack.
Сдвиг: twoBack = oneBack, затем oneBack = current.
Верните oneBack.

def numDecodings(s):
    # ways(i) counts the readings of the first i digits; ways(0) = 1.
    two_back, one_back = 0, 1  # ways(i-1) and ways(i) before digit i is read
    for i in range(len(s)):
        current = 0
        if s[i] != "0":
            current = one_back  # digit i is a letter on its own
        if i >= 1 and s[i - 1] != "0" and int(s[i - 1:i + 1]) <= 26:
            current += two_back  # digits i-1 and i form one letter, 10 to 26
        two_back, one_back = one_back, current
    return one_back

Ловушки и крайние случаи

Считать 0 буквой или трактовать 06 как 6. У "30", "100" и "06" число прочтений равно 0.
Проверять двухзначный фрагмент только по условию ≤ 26. 05 — это число 5, но не код, поэтому проверь, что его первая цифра не 0.
Помечать неизвестные слоты мемоизации числом 0. Позиции с 0 прочтениями тогда никогда не считаются сохранёнными: при 44 единицах, 55 тройках и завершающем 0 снова потребуется около 10^11 вызовов.
Читать цифру перед индексом 0. Ограничь проверку двух цифр условием i ≥ 1; в Python s[-1] незаметно считывает последнюю цифру.
Преобразовывать s в одно число. Сто цифр не помещаются ни в один целочисленный тип, а ведущие нули, которые меняют ответ, теряются.

Частые вопросы3

Какова временная сложность задачи Decode Ways?

Решение снизу вверх считывает каждую цифру один раз за постоянное время: O(n) времени и O(1) дополнительной памяти. Рекурсия с мемоизацией также требует O(n) времени, но использует O(n) памяти. Обычная рекурсия имеет экспоненциальную сложность: для строки из единиц количество вызовов растёт примерно как 1.618^n.

Как задача Decode Ways связана с задачей Climbing Stairs?

Оба способа подсчитывают количество вариантов пройти отрезок шагами длиной 1 и 2. В задаче Climbing Stairs допустим каждый шаг, поэтому количество вариантов соответствует числам Фибоначчи. В задаче Decode Ways для шага из одной цифры требуется число от 1 до 9, а для шага из двух цифр — от 10 до 26, поэтому каждое слагаемое добавляется, только если выполняется соответствующее условие.

Как обрабатывать нули в задаче Decode Ways?

0 никогда не является отдельной буквой, поэтому он должен сочетаться с предшествующей цифрой, образуя 10 или 20. Он добавляет количество из двух цифр назад только после 1 или 2, а в остальных случаях — ничего. Начальный 0, два нуля подряд или 0 после числа от 3 до 9 дают 0.

def numDecodings(s):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

s = "2611"

Ожидаемый вывод

Decode Ways

Функция

Ограничения

Примеры

Подсказки

Решение

Попробуйте оба прочтения с рекурсией

Рекурсия с мемоизацией

Снизу вверх с двумя счётчиками

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи