91. Decode Ways

문제링크: https://leetcode.com/problems/decode-ways/

A~Z까지 문자에 1~26의 고유 번호가 있다. 주어진 숫자열을 보고 문자로 변환할 때, 가능한 경우의 수에 대해 구하는 문제다.

Solution

Dynamic programming

숫자는 최대 두자리수까지 알파벳으로 변환될 수 있다. 따라서 숫자열 하나를 바꾸는 방식, 두개를 바꾸는 방식이 존재한다. 어느 i지점까지 경우의 수를 계산할 수 있다면 i+1지점은 i지점 + 하나의 숫자 또는 i-1지점 + 두개의 숫자 두가지 방식이 모두 가능하다. 따라서 추가되는 숫자에 따라서 다음과 같은 점화식을 세울 수 있다.

result[i + 1] = IF( i + 1 이 단일 문자가 가능) result[i] + IF(i ~ i + 1 두자리 숫자로 문자가 가능) result[i - 1]

위 수식을 통해 피보나치와 비슷하게 DP를 구현할 수 있다.

Algorithm

• 숫자가 총 26개로 변하지 않기 때문에 가능한 숫자 판별을 위해 공간을 사용해 Set으로 판별한다.
• s의 길이가 없거나 1자리면 바로 결과를 반환한다. (초기조건 이후 반복이 불가능하기 때문)
• mem[0] 과 mem[1]을 직접 판별해 저장한다.(초기값)
• 위 수식을 이용해 한자리가 가능할 시+mem[i-1], 두 자리가 가능할 시 +mem[i-2]를 반복한다.
• 마지막까지 반복한 결과를 반환한다.

var numDecodings = function(s) {
  // DP iteration
  const one = new Set(['1', '2', '3', '4','5', '6', '7', '8', '9']);
  const two = new Set(['10', '11', '12','13','14','15','16','17','18','19','20','21','22','23','24','25','26']);
  
  if (s[0] === '0') return 0;
  if (s.length === 1) return 1;
  const mem = new Array(s.length).fill(0);
  
  mem[0] = 1;
  if (one.has(s[1])) mem[1]++;
  if (two.has(s[0] + s[1])) mem[1]++;
  // Iterate
  for (let i = 2; i < s.length; i++) {
    if (one.has(s[i])) mem[i] += mem[i - 1];
    if (two.has(s[i - 1] + s[i])) mem[i] += mem[i - 2];
  }
  return mem[s.length - 1];
};