LeetCode 명상: 디코드 방법

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

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

"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.length <= 100
• 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;




<p>이전 문제와 마찬가지로 아래쪽 두 값을 유지해야 하므로 문자열의 첫 번째 문자를 디코딩하는 방법 수에 해당하는 배열의 두 번째 슬롯을 초기화해야 합니다.</p>

<p>'0'이면 디코딩할 수 없다는 것을 알고 있으므로, 이 경우 디코딩하는 방법의 횟수는 0이 됩니다.<br>
<em>디코딩할 수 없다는</em> 것은 <em>디코딩을 전혀 하지 않는</em> 것과 다릅니다. 첫 번째 경우에는 디코딩 방법의 수가 0이지만 두 번째 경우에는 방금 dp[0])으로 했으니, 디코딩하는 방법의 수는 1이라고 할 수 있습니다.</p>

<p>다른 모든 경우에는 단일 문자이기 때문에 디코딩하는 방법은 <strong>한 가지</strong>뿐입니다. 따라서 그에 따라 dp[1]을 초기화하겠습니다.<br>
</p>

<pre class="brush:php;toolbar:false">dp[1] = (s[0] === '0') ? 0 : 1;

이제 세 번째 인덱스부터 반복을 시작할 수 있습니다. 이전 숫자와 이전 두 숫자를 동시에 살펴보겠습니다.

이전 숫자가 숫자 0이 아닌 한 배열의 이전 슬롯에 있는 것을 무엇이든 추가할 수 있습니다.

그리고 앞의 두 자리 숫자가 10에서 26 사이의 숫자라면 해당 솔루션도 추가할 수 있습니다. 전체적으로 다음과 같이 보일 수 있습니다.

for (let i = 2; i <= s.length; i++) {
  const prevDigit = s[i - 1];
  const twoPrevDigits = s.slice(i - 2, i);
  if (+prevDigit !== 0) {
    dp[i] += dp[i - 1];
  }

  if (10 <= +twoPrevDigits && +twoPrevDigits <= 26) {
    dp[i] += dp[i - 2];
  }
}

Note

We're converting the string characters to numbers with the handy unary plus operator. We know from the problem constraints that the string s only contains digits.

At this point, we have the result in the last index (which corresponds to s.length) so we can just return it:

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

  return dp[s.length]; 
}

Overall, this is how our solution looks like:

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 <= s.length; i++) {
    const prevDigit = s[i - 1];
    const twoPrevDigits = s.slice(i - 2, i);
    if (+prevDigit !== 0) {
      dp[i] += dp[i - 1];
    }

    if (10 <= +twoPrevDigits && +twoPrevDigits <= 26) {
      dp[i] += dp[i - 2];
    }
  }

  return dp[s.length];
}

Time and space complexity

Both the time and space complexity for this solution are $O(n)$O(n) as we iterate through all the characters doing a constant operation, and we have to keep an array whose size will grow as our input size increases.

---

Next up is the problem called Coin Change. Until then, happy coding.

위 내용은 LeetCode 명상: 디코드 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!