<Medium> Decode Ways (LeetCode : C#)

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

📕 문제 설명

숫자로 이루어진 문자열이 주어질 때 decode 가능한 방법의 수 반환하기

기본적으로 문자는 다음과 같이 인코딩 된다.

A -> 1
B -> 2
.
.
Z -> 26

숫자로 이루어진 문자열들을 어떻게 쪼개서 decode하느냐에 따라 다양한 조합이 나온다!

• Input
  숫자로 이루어진 문자열 (string)
• Output
  decode 가능한 방법의 수 (int)

예제

풀이

맨 마지막을 1로 초기화 하고, 앞으로 가면서 1자리수가 가능하다면 뒤에거 그대로 가져온 상태에서 2자리수도 가능하면 2개 뒤로 나오는 것도 더해주기

public class Solution {
    public int NumDecodings(string s) {
        var dp = new int[s.Length+1];
        dp[s.Length] = 1;

        for (int i = s.Length-1; i >= 0; i--)
        {
            if (s[i] == '0') 
            {
                dp[i] = 0;
            }
            else
            {
                dp[i] = dp[i + 1];
            }

            if (i + 1 < s.Length && (s[i] == '1' || s[i] == '2' && s[i + 1] <= '6')) // 2자리수 가능한 경우
            {
                dp[i] += dp[i + 2];
            }
        }
        return dp[0];
    }
}

결과