[leetcode]91. Decode Ways

https://leetcode.com/problems/decode-ways/

문자열이 주어졌을 때, 각 숫자를 알파벳(A=1, B=2, … Z=26)으로 디코딩할 수 있는 경우의 수를 구하는 문제다.

문제 핵심

• 1글자씩 혹은 2글자씩 끊어 디코딩 가능하다.
• '0'은 단독으로 디코딩 불가능하고, ‘10’, ‘20’처럼 특정 경우에만 유효하다.

DP 접근법

• dp[i] = s의 처음부터 i번째 문자까지 디코딩 가능한 경우의 수
• 시작: dp[0] = 1 (빈 문자열 디코딩 방법 1가지)

점화식

dp[i] = 0
if 한 글자(s[i-1])가 1~9면 dp[i] += dp[i-1]
if 두 글자(s[i-2..i-1])가 10~26면 dp[i] += dp[i-2]

• dp[0] = 1은 빈 문자열에서 시작하는 경로 수
• dp[n]은 전체 문자열 디코딩 가능한 경우의 수
• 이전 계산(dp[i-1], dp[i-2])을 바탕으로 현재 자리(dp[i]) 계산

코드

function numDecodings(s) {
  if (s[0] === '0') return 0;
  const n = s.length;
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1; dp[1] = 1;
  
  for (let i = 2; i <= n; i++) {
    const one = Number(s.slice(i-1, i));
    const two = Number(s.slice(i-2, i));
    if (one >= 1 && one <= 9) dp[i] += dp[i-1];
    if (two >= 10 && two <= 26) dp[i] += dp[i-2];
  }
  return dp[n];
}