Давайте начнем с описания этой проблемы:

Вы перехватили секретное сообщение, закодированное в виде строки цифр. Сообщение декодируется с помощью следующего сопоставления:

"1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z'

Однако при декодировании сообщения вы понимаете, что существует много разных способов декодирования сообщения, поскольку некоторые коды содержатся в других кодах («2» и «5» против «25»).

Например, «11106» можно декодировать как:

• «AAJF» с группировкой (1, 1, 10, 6)
• «KJF» с группировкой (11, 10, 6)
• Группировка (1, 11, 06) недействительна, поскольку «06» не является допустимым кодом (действителен только «6»).

Примечание: могут существовать строки, которые невозможно декодировать.

Дана строка s, содержащая только цифры, вернуть количество способов ее декодировать. Если всю строку невозможно декодировать каким-либо допустимым способом, верните 0.

Тестовые примеры генерируются таким образом, чтобы ответ умещался в 32-битное целое число.

Например:

Input: s = "12"

Output: 2

Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Или:

Input: s = "226"

Output: 3

Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Или:

Input: s = "06"

Output: 0

Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a valid encoding, so return 0.

Ограничения:

• 1
• s содержит только цифры и может содержать ведущие нули.

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

Во-первых, давайте начнем с самого простого: символ может быть декодирован как сам по себе (как один символ), так и как часть двузначного числа.
Если это первый вариант, мы можем использовать только цифры от 1 до 9, поскольку 0 сам по себе ни с чем не сопоставляется.
Однако двузначное число может быть от 10 до 26.

Как и в случае с предыдущими задачами в этой главе, мы можем начать с создания массива dp, в котором будет храниться количество способов декодирования каждого символа при проходе по строке.
Очень похоже на «Подъем по лестнице»: нам нужно инициализировать наш массив длиной s.length 1, поскольку нам нужно учитывать тот факт, что мы еще ничего не декодировали.
Другими словами, когда символов нет, есть только один способ «декодировать»: вообще не декодировать.

Итак, мы можем инициализировать все значения нулями, за исключением первого индекса, который будет равен 1.

let dp = Array.from({ length: s.length   1 }, () => 0);

dp[0] = 1;

Опять же, как и в предыдущих задачах, нам нужно сохранить два нижних значения, поэтому нам нужно инициализировать второй слот нашего массива, который соответствует количеству способов декодирования первого символа в строке.

Мы знаем, что не сможем декодировать его, если он равен «0», поэтому количество способов его декодирования в этом случае будет равно 0.
Обратите внимание, что неспособность декодировать отличается от не делать никакого декодирования вообще: в первом случае количество способов декодирования равно 0, но во втором случае (так как мы только что сделали с dp[0]), можно сказать, что количество способов декодирования равно 1.

Во всех остальных случаях существует только один способ его декодирования, поскольку это всего лишь один символ. Итак, мы инициализируем dp[1] соответственно:

dp[1] = (s[0] === '0') ? 0 : 1;

Теперь мы можем начать итерацию с третьего индекса. Мы рассмотрим одновременно предыдущую цифру и две предыдущие цифры.

Пока предыдущая цифра не равна 0, мы можем добавить все, что находится в предыдущем слоте нашего массива.

И поскольку предыдущие две цифры представляют собой число от 10 до 26, мы также можем добавить это соответствующее решение. В целом это может выглядеть так:

for (let i = 2; i 



Примечание
Мы преобразуем строковые символы в числа с помощью удобного унарного оператора плюс. Из ограничений задачи мы знаем, что строка s содержит только цифры.


На данный момент у нас есть результат в последнем индексе (который соответствует s.length), поэтому мы можем просто вернуть его:


function numDecodings(s: string): number {
  /* ... */

  return dp[s.length]; 
}




В целом, вот как выглядит наше решение:


function numDecodings(s: string): number {
  let dp = Array.from({ length: s.length   1 }, () => 0);

  dp[0] = 1;
  dp[1] = (s[0] === '0') ? 0 : 1;

  for (let i = 2; i 




  
  
  Временная и пространственная сложность


И временная, и пространственная сложность этого решения $O(n)$На)

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


Следующая проблема под названием Coin Change. А пока удачного программирования.