LeetCode 91

여기서 주의할 점은 "0"에 대한 처리이다. "06"은 어떤 알파벳으로도 바꿔 줄수 없으므로 답은 0이 나온다. 처음에 생각한 방식은 "11106"이 들어오면 첫 문자열 부터 순회를 하면서 dp[i] = (i까지의 총 만들 수 있는 개수)로 생각하고 시작하였다.

일단 예외 사항으로 첫글자부터 "0"이 나오면 그 수는 만드는게 불가능하다.
또한 "30" 처럼 두 글자가 시작하면 이러한 숫자도 만드는게 불가능하다.
여기에 대한 예외처리를 미리 해준다.

그 이외에는 dp[0]=1 을 해주고 "28" 같은 경우는 dp[1] = dp[0], "21" 같은 경우는 dp[1] = dp[0]+1 을 해준다.

i=2 부터 순회를 시킨다.
s의 i-1부터 i까지의 글자가 0이 들어가지 않고 26보다 작은 경우, 예를 들어 "13" 이런 경우는 dp[i] = dp[i-1] + dp[i-2] 를 해준다.

1214인 경우를 생각해보자 현재 i는 3이다. 생각해 볼 숫자는 14인데 이 숫자는 26보다 작으므로 14로 알파벳 변환이 가능하다.
14가 알파벳인 경우 => 12를 변환하는 방법 = dp[i-2]
1,4 각각 알파벳인 경우 => 121를 변환하는 방법 = dp[i-1]

s의 i-1부터 i까지의 글자가 0이 들어가지 않고 26보다 큰 경우는
dp[i]=dp[i-1]

1234 인 경우를 생각해보자 i는 3이다. 34는 알파벳으로 만들 수 없으므로
3,4 따로 만들어줘야 한다. 따라서 123을 변환시키는 방법에 뒤에 4가 그대로 붙는다.

문제는 s의 i-1 부터 i까지의 글자가 0이 들어가는 경우이다.
case 1) 잘린 s가 "06" 일 경우 06을 한꺼번에 처리할 수 없으므로 0앞에 숫자가 처리해줘야 한다. 따라서 이 경우는 dp[i] = dp[i-1]

case 2) 잘린 s가 "?0" 인경우
=> 1. "20" 이런 경우는 무조건 20 한꺼번에 처리해 줘야 하므로 2앞 이전까지 의 방법의 개수를 그대로 사용한다. dp[i]=dp[i-2]

case 3) 잘린 s가 "00" 인경우
=> 말할 것도 없이 return 0 을 처리해 준다.

var numDecodings = function(s) {
    let dp = new Array(s.length).fill(0);
    if(s[0] === "0" || (s[1] === "0" && Number(s[0]+s[1])>26)) return 0;
    dp[0]=1;
    
    dp[1] = 
      s.slice(0,2)[1]!== "0" &&Number(s.slice(0,2)) <=26 ? 2 : 1;
  
    for(let i=2; i<s.length;i++){
        const filterNum = s.slice(i-1,i+1);
        const Num = Number(s.slice(i-1,i+1));
        if(filterNum[1] === "0" && filterNum[0] !== "0"){
            if(Num <=26) dp[i] =  dp[i-2];
            else return 0;
            
        } else if(filterNum[1] !== "0" && filterNum[0] ==="0"){
          dp[i]=dp[i-1];
        }else if(filterNum === "00"){
            return 0;     
        }else if(Num <=26){
              dp[i]=dp[i-1]+dp[i-2];   
        }else{
            dp[i]=dp[i-1];
        }
    }
    return dp[s.length-1];
};

코드가 많이 지저분하다 생각한다....

다른 사람의 풀이다.

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];
}