[알고리즘] LeetCode -Decode Ways
LeetCode - Decode Ways
문제 설명
A message containing letters from A-Z can be encoded into numbers using the following mapping:
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:
"AAJF" with the grouping (1 1 10 6)
"KJF" with the grouping (11 10 6)
Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".
Given a string s containing only digits, return the number of ways to decode it.
The answer is guaranteed to fit in a 32-bit integer.
Example 1:
Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Example 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.
Example 4:
Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").
Constraints
1 <= s.length <= 100
s contains only digits and may contain leading zero(s).
Solution
/**
* @param {string} s
* @return {number}
*/
var numDecodings = function (s) {
let sCountArray = [];
let sLen = s.length;
if (s[0] == '0') {
return 0;
}
sCountArray.push(1);
for (let i = 1; i < sLen; i++) {
let num = Number(s[i]);
if (num == 0) { // i 번째 숫자가 0인 경우,
if ((Number(s[i - 1]) <= 0 || Number(s[i - 1]) > 2)) { // 앞의 숫자가 1,2가 아닌경우
return 0;
}
// 20124
sCountArray.push(sCountArray[i - 1]);
//1 혹은 2면 promise
}
else { // i번째 숫자가 0이 아닌경우,
let preNum = Number(s[i - 1]);
if ((preNum == 1) || (preNum == 2 && num <= 6)) { // 십의자리로 변환 가능한 숫자이면
if (i + 1 < sLen && Number(s[i + 1]) == 0) { // 뒤에 0이 있는 경우엔 이 앞의 숫자와 십의자리 매칭을 하면 안되므로
sCountArray.push(sCountArray[i - 1]);
}
else {
if (i - 2 >= 0) {
let twoPreNum = Number(s[i - 2]);
if (twoPreNum == 1 || twoPreNum == 2) {
sCountArray.push(sCountArray[i - 1] + sCountArray[i - 2]); // sCountArray[i-2]*2 + sCountArray[i-1] - sCountArray[i-2]
// [i-2]번째까지 경우의 수는, i번째가 i-1번째와 십의자리 매칭을 하냐 안하냐의 따라서 경우가 나눠지므로 : sCountArray[i-2]*2
// [i-2]번째까지 경우의 수는에는 [i-2]번째와 [i-1]번째가 결합한 경우의 수가 제외되어있기 때문에 추가 고려해준다: sCountArray[i-1] - sCountArray[i-2]
}
else {
sCountArray.push(sCountArray[i - 2] * 2);
}
}
else {
sCountArray.push(2);
}
}
}
else {
sCountArray.push(sCountArray[i - 1]);
}
}
}
return sCountArray[sLen - 1];
};
A message containing letters from A-Z can be encoded into numbers using the following mapping:
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:
"AAJF" with the grouping (1 1 10 6)
"KJF" with the grouping (11 10 6)
Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".
Given a string s containing only digits, return the number of ways to decode it.
The answer is guaranteed to fit in a 32-bit integer.
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 = "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.
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).
/**
* @param {string} s
* @return {number}
*/
var numDecodings = function (s) {
let sCountArray = [];
let sLen = s.length;
if (s[0] == '0') {
return 0;
}
sCountArray.push(1);
for (let i = 1; i < sLen; i++) {
let num = Number(s[i]);
if (num == 0) { // i 번째 숫자가 0인 경우,
if ((Number(s[i - 1]) <= 0 || Number(s[i - 1]) > 2)) { // 앞의 숫자가 1,2가 아닌경우
return 0;
}
// 20124
sCountArray.push(sCountArray[i - 1]);
//1 혹은 2면 promise
}
else { // i번째 숫자가 0이 아닌경우,
let preNum = Number(s[i - 1]);
if ((preNum == 1) || (preNum == 2 && num <= 6)) { // 십의자리로 변환 가능한 숫자이면
if (i + 1 < sLen && Number(s[i + 1]) == 0) { // 뒤에 0이 있는 경우엔 이 앞의 숫자와 십의자리 매칭을 하면 안되므로
sCountArray.push(sCountArray[i - 1]);
}
else {
if (i - 2 >= 0) {
let twoPreNum = Number(s[i - 2]);
if (twoPreNum == 1 || twoPreNum == 2) {
sCountArray.push(sCountArray[i - 1] + sCountArray[i - 2]); // sCountArray[i-2]*2 + sCountArray[i-1] - sCountArray[i-2]
// [i-2]번째까지 경우의 수는, i번째가 i-1번째와 십의자리 매칭을 하냐 안하냐의 따라서 경우가 나눠지므로 : sCountArray[i-2]*2
// [i-2]번째까지 경우의 수는에는 [i-2]번째와 [i-1]번째가 결합한 경우의 수가 제외되어있기 때문에 추가 고려해준다: sCountArray[i-1] - sCountArray[i-2]
}
else {
sCountArray.push(sCountArray[i - 2] * 2);
}
}
else {
sCountArray.push(2);
}
}
}
else {
sCountArray.push(sCountArray[i - 1]);
}
}
}
return sCountArray[sLen - 1];
};
~.~
Author And Source
이 문제에 관하여([알고리즘] LeetCode -Decode Ways), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jerry92/알고리즘-LeetCode-Decode-Ways저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)