이 문제에 대한 설명부터 시작해 보겠습니다.

숫자열로 인코딩된 비밀 메시지를 가로채었습니다. 메시지는 다음 매핑을 통해 디코딩됩니다.

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

그러나 메시지를 디코딩하는 동안 일부 코드가 다른 코드("2" 및 "5" 대 "25")에 포함되어 있기 때문에 메시지를 디코딩할 수 있는 다양한 방법이 있다는 것을 알게 됩니다.

예를 들어 "11106"은 다음으로 디코딩될 수 있습니다.

• 그룹화(1, 1, 10, 6)가 포함된 "AAJF"
• 그룹화(11, 10, 6)가 포함된 "KJF"
• '06'은 유효한 코드가 아니기 때문에 그룹화(1, 11, 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에는 숫자만 포함되며 앞에 0이 포함될 수 있습니다.

직접 풀어보기 전까지는 얼핏 그리 어렵지 않다고 생각되는 문제 중 하나라고 생각합니다.

먼저 가장 간단한 통찰력부터 시작해 보겠습니다. 문자는 그 자체(단지 한 문자) 또는 두 자리 숫자의 일부로 디코딩될 수 있습니다.
첫 번째 옵션인 경우 0 자체는 아무 것도 매핑되지 않으므로 1에서 9까지의 숫자만 가질 수 있습니다.
단, 두 자리 숫자는 10부터 26까지 가능합니다.

이 장의 이전 문제와 마찬가지로 문자열을 반복하면서 각 문자까지 디코딩하는 방법의 수를 보유하는 dp 배열을 만드는 것부터 시작할 수 있습니다.
Climbing Stairs와 매우 유사하며, 아직 아무것도 디코딩하지 않았다는 사실을 고려해야 하기 때문에 길이 s.length 1로 배열을 초기화해야 합니다.
즉, 문자가 없을 때 "디코딩"하는 방법은 한 가지뿐입니다. 즉, 전혀 디코딩하지 않는 것입니다.

따라서 첫 번째 인덱스가 1이 되는 것을 제외하고 모든 값을 0으로 초기화할 수 있습니다.

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)라는 문제입니다. 그때까지 즐거운 코딩하세요.