Постановка задачи
Сообщение, содержащее буквы от A до Z, можно закодировать в числа, используя следующее сопоставление:
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"Чтобы декодировать закодированное сообщение, все цифры должны быть сгруппированы, а затем преобразованы обратно в буквы с использованием обратного сопоставления выше (может быть несколько способов). Например, "11106" можно преобразовать в:
"AAJF" with the grouping (1 1 10 6)"KJF" with the grouping (11 10 6)
Обратите внимание, что группировка (1 11 06) недействительна, потому что «06» не может быть преобразовано в «F», так как «6» отличается от «06».
Получив строку s, содержащую только цифры, возвратите количество способов ее декодирования.
Ответ гарантированно помещается в 32-битное целое число.
Постановка задачи взята с: https://leetcode.com/problems/decode-ways
Пример 1:
Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).Пример 2:
Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).Пример 3:
Input: s = "0"
Output: 0
Explanation: There is no character that is mapped to a number starting with 0.
The only valid mappings with 0 are 'J' -> "10" and 'T' -> "20", neither of which start with 0.
Hence, there are no valid ways to decode this since all digits need to be mapped.Пример 4:
Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").Ограничения:
- 1 <= s.length <= 100
- s contains only digits and may contain leading zero(s).Объяснение
Решение грубой силы
Наивный подход состоит в том, чтобы сгенерировать все возможные комбинации и подсчитать количество правильных последовательностей.
Этот подход легко реализовать, но его временная сложность составляет O(2^N).
Динамическое программирование
Проблема может быть решена с использованием подхода динамического программирования.
Возьмем строку "12". Мы можем декодировать строку двумя способами: [1, 2] или 12. Теперь добавим 6 в конец строки. Для новой строки способы декодирования 2 + 1 = 3. 2 для [1, 2, 3] или [12, 3] и 1 для [1, 23].
Сначала мы решили подзадачу и использовали ее решение для решения большей проблемы. Это не что иное, как подход динамического программирования.
Проверим алгоритм.
- initialize count array: count[n + 1] - set count[0] = count[1] = 1- if s[0] == 0 // first character of string is 0 - return 0- loop for i = 2; i <= n; i++ - set count[i] = 0// if string is "02" we should not count "02" as a valid case. // But if the previous char is greater than 0 we set the current index count same // as the previous index count. - if s[i - 1] > '0' - count[i] = count[i - 1]// if string is "32" it is not possible to map to any character. // hence we have (i - 2)th index for 1 or 2 and // if s[i - 2] is 2 we additionally check for (i - 1)th index to // be less than 7. - if s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] < '7') - count[i] += count[i - 2]- return count[n]
С++ решение
class Solution { public: int countWays(string s, int n){ int count[n + 1]; count[0] = 1; count[1] = 1;if(s[0] == '0') return 0;for(int i = 2; i <= n; i++){ count[i] = 0;if(s[i - 1] > '0') count[i] = count[i - 1];if(s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] < '7')){ count[i] += count[i - 2]; } }return count[n]; }public: int numDecodings(string s) { return countWays(s, s.size()); } };
Голанг решение
func numDecodings(s string) int { count := make([]int, len(s) + 1) count[0], count[1] = 1, 1if s[0] == '0' { return 0 }for i := 2; i <= len(s); i++ { if s[i - 1] > '0' { count[i] = count[i - 1] }if s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] < '7') { count[i] += count[i - 2] } }return count[len(s)] }
Javascript-решение
var numDecodings = function(s) { let count = []; count[0] = 1; count[1] = 1;for(let i = 2; i <= s.length; i++){ count[i] = 0;if(s[i - 1] > '0'){ count[i] = count[i - 1]; }if(s[i - 2] == '1' || (s[i - 2]) == '2' && s[i - 1] < '7'){ count[i] += count[i - 2]; } }return count[s.length]; };
Давайте запустим наш алгоритм в пробном режиме, чтобы увидеть, как работает решение.
Input: s = "226"
Step 1: int count[n + 1]
count[0] = count[1] = 1
Step 2: if s[0] == '0'
'2' == '0'
false
Step 3: loop for i = 2; i <= n;
2 <= 3
true
if s[i - 1] > '0'
s[2 - 1] > '0'
s[1] > '0'
'2' > '0'
true
count[i] = count[i - 1]
count[2] = count[2 - 1]
= count[1]
= 1
if s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] < '7'))
s[2 - 2] == '1'
s[0] == '1'
'2' == '1'
false
s[i - 2] == '2' && s[i - 1] < '7'
s[2 - 2] == '2' && s[2 - 1] < '7'
s[0] == '2' && s[1] < '7'
'2' == '2' && '2' < '7'
true
count[2] = count[i] + count[i - 2]
= count[2] + count[2 - 2]
= 1 + 1
= 2
i++
i = 3
Step 4: loop for i <= n;
3 <= 3
true
if s[i - 1] > '0'
s[3 - 1] > '0'
s[2] > '0'
'6' > '0'
true
count[i] = count[i - 1]
count[3] = count[3 - 1]
= count[2]
= 2
if s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] < '7'))
s[3 - 2] == '1'
s[1] == '1'
'2' == '1'
false
s[i - 2] == '2' && s[i - 1] < '7'
s[3 - 2] == '2' && s[3 - 1] < '7'
s[1] == '2' && s[2] < '7'
'2' == '2' && '6' < '7'
true
count[3] = count[i] + count[i - 2]
= count[3] + count[3 - 2]
= 2 + 1
= 3
i++
i = 4
Step 5: loop for i <= n;
4 <= 3
false
Step 6: return count[n]
count[3] = 3
So the answer we return is 3.Первоначально опубликовано на https://alkeshghorpade.me.
