Decode Ways

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

0 никогда не может быть буквой само по себе, поэтому оно должно сочетаться с цифрой перед ним, и только 10 и 20 являются кодами. В цикле снизу вверх это означает, что 0 ничего не добавляет в случае одной цифры и добавляет количество вариантов для двух цифр назад только после 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 не является кодом, поэтому ни одно сообщение не даёт эту строку.

+25 скрытых тестов при отправке

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

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

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

Идея

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

Для "2611": первая буква — это 2 или 26. После 2 следующей буквой может быть только 6, потому что 61 — слишком большое число. Обе ветви затем заканчиваются на 1 1 или 11, поэтому всего получается 2 × 2 = 4.

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

Алгоритм

Напиши вспомогательную функцию waysFrom(i), которая подсчитывает варианты расшифровки цифр от индекса i до конца.
Если i равен длине s, верни 1.
Если цифра на позиции i равна 0, верни 0.
Начни с waysFrom(i+1) — вариантов расшифровки, в которых следующая буква соответствует одной цифре.
Если цифры на позициях i и i+1 образуют число не больше 26, прибавь waysFrom(i+2). Верни 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. Сохраняй каждый подсчёт в массиве memo при первом вычислении, а затем считывай его оттуда.

Помечай невычисленные ячейки значением -1, а не 0. Здесь ноль — это реальный ответ: в строке, заканчивающейся на 30, у каждой позиции 0 способов прочтения. Если использовать 0 как метку, при каждом посещении эти позиции будут выглядеть неизвестными, и рекурсия останется такой же медленной, как прежде.

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

Алгоритм

Создай массив memo с одним элементом для каждого индекса и установи для всех значение -1.
В waysFrom(i) возвращай 1 в конце строки, а если значение не равно -1, возвращай memo[i].
В противном случае считай, как при обычной рекурсии: 0 для 0, иначе waysFrom(i+1) плюс waysFrom(i+2), если две цифры образуют число от 10 до 26.
Сохрани количество в memo[i], включая ноль, и верни его.
Верни waysFrom(0).

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(i) — это сумма вариантов, для которых выполняется условие. У пустого префикса один вариант прочтения — пустое сообщение, поэтому ways(0) = 1.

Разберём "1203". После 1 количество вариантов равно 1. После 12 оно равно 2: 1 2 и 12. 0 не может стоять отдельно, и подходит только 20, поэтому количество вариантов возвращается к значению до 2, то есть становится равным 1. 3 может стоять отдельно, а 03 не является кодом, поэтому количество вариантов остаётся равным 1.

Для каждого количества нужны только два предыдущих значения, поэтому таблицу заменяют две переменные: twoBack и oneBack. Это один проход с постоянным объёмом работы для каждой цифры: время O(n), память O(1) и никакой рекурсии.

Алгоритм

Задайте twoBack = 0 и oneBack = 1 — количество способов для пустого префикса.
Для каждого индекса i задайте начальное значение current равным 0 и прибавьте oneBack, если цифра i не равна 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. Ноль может завершать только 10 или 20, поэтому для "30", "100" и "06" есть 0 вариантов расшифровки.
Проверять, что двухзначная часть не больше 26, и на этом останавливаться. Число 05 равно 5, но это не код. Проверь, что первая из двух цифр не равна 0.
Использовать 0 как отметку для ещё не вычисленной ячейки мемоизации. Во многих позициях действительно бывает 0 вариантов расшифровки, поэтому такие ячейки никогда не считаются сохранёнными, и вычисления повторяются при каждом обращении. Для 44 единиц, за которыми следуют тройки и завершающий 0, во всех ячейках будет 0, и количество вызовов снова составит примерно 10^11.
Считывать цифру перед индексом 0. Ограничь проверку двухзначного числа условием i ≥ 1: в Python s[-1] незаметно считывает последнюю цифру, а другие языки обращаются за пределы строки.
Преобразовывать s в одно число. Сто цифр не помещаются ни в один целочисленный тип, а при преобразовании удаляются ведущие нули, которые меняют ответ. Обрабатывай цифры по одной.
В Lua и R позиции начинаются с 1, поэтому конец строки — позиция n+1, а первая проверка двухзначного числа выполняется на позиции 2.

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

Какова временная сложность алгоритма 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 являются кодами. В цикле снизу вверх это означает, что 0 ничего не добавляет в случае одной цифры и добавляет количество вариантов для двух цифр назад только после 1 или 2. Начальный 0, два нуля подряд или 0 после цифры от 3 до 9 дают ответ 0.

Можно ли решить задачу Decode Ways за O(1) дополнительной памяти?

Да. Количество для префикса зависит только от количеств для двух префиксов, которые короче на одну и две цифры, поэтому две переменные заменяют всю таблицу. На каждом шаге вычисляется новое количество на их основе, а затем они сдвигаются на одну позицию.

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

s = "2611"

Ожидается

Decode Ways

Функция

Ограничения

Примеры

Подсказки

Решение

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

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

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

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

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

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