[LeetCode] 91. Decode Ways

😎풀이

dp의 개념을 파악하고 있다면 풀이가 어렵지 않다.

문제에서 요구하는 경우의 수가 딱 두개이기 때문

한자리 수가 이룰 수 있는 경우의 수
두자리 수를 붙여 이룰 수 있는 경우의 수

function numDecodings(s: string): number {
    if(!s.length) return 0;
    if(s[0] === '0') return 0;

    // N 번째 문자열이 가능한 decode 수
    const dp = Array.from({length: s.length + 1}, () => 0);

    dp[0] = 1;
    dp[1] = 1;

    for(let i = 2; i <= s.length; i++) {
        // 한 자리만 변환
        const oneDigit = parseInt(s.slice(i - 1, i))
        // 두 자리를 변환
        const twoDigit = parseInt(s.slice(i - 2, i))
        // 경우의 수 합계
        if(oneDigit >= 1 && oneDigit <= 9) dp[i] += dp[i - 1]
        if(twoDigit >= 10 && twoDigit <= 26) dp[i] += dp[i - 2]
    }
    
    return dp[s.length]
};