Leetcode 91. Decode ways

function numDecodings(s) {
  if (s.length === 0) return 0;
  const N = s.length;
  const dp = Array(N+1).fill(0);

  dp[0] = 1;
  dp[1] = s[0] === '0' ? 0 : 1;

  for (let i = 2; i <= N; i++) {
    if (s[i-1] !== '0') {
      dp[i] += dp[i-1];
    }
    if (s[i-2] === '1' || s[i-2] === '2' && s[i-1] <= '6') {
      dp[i] += dp[i-2];
    }
  }

  return dp[N];
}

 

dp 테이블의 길이를 문자열의 길이 + 1 로 초기화 해줍니다.

예를 들어 dp[1]은 한자리 문자열의 가능한 개수이고, dp[2]는 2자리 문자열까지 가능한 개수이다.

 

1자리 또는 2자리를 붙여서 다른자리를 만든다고 생각하면

 

dp[i] = dp[i -1] + dp[i - 2] 이다. 이 이유는 dp[i]는 i번째자리까지의 가지수이므로 dp[i - 1] 까지의 가짓수에서 숫자하나를 붙인것에 불과하므로 dp[i] = d[i - 1]이다. 근데 dp[i-2]에서 한번에 두칸을 붙일 수도 있으므로 d[i] = dp[i - 1] + dp[i -2] 이다. 

 

dp[0]이 1인 이유는 빈문자열에서 문자열을 합해나갈 때 빈문자열을 1개있는거로 취급해야 되기 때문이다.

예를 들어서 "" + "12" => "12"인데 "12"를 한번에 만들었다고 생각해야하는 것이다.

 

하지만 여기서 조건이 들어간다. 어떤 문자열의 자리가 0이면 그대로 못붙이고 그전 자리까지의 경우의 수의 합을 더할 수 없다.

하지만 문자열이 0이 아니면 그전자리의 경우의 수를 그대로 가져올 수 있다.