[LeetCode] 91 - Decode Ways

문제

• 링크: https://leetcode.com/problems/decode-ways
• 난이도: Medium
• 태그: 문자열, 다이내믹 프로그래밍
• 결과: Time: 0 ms (100%), Space: 8.29 MB (96.34%)

풀이

class Solution {
public:
    int numDecodings(string s) {
        int d[101];
        int len = s.size();

        if (s[0] == '0') // 0으로 시작할 수 없음
        {
            return 0;
        }

        d[0] = 1; // 빈 문자열 -> 1가지 방법
        d[1] = 1; // 첫 문자 -> 1가지 방법 (0이 아닌건 확인했음)

        for (int i = 2; i <= len; ++i) 
        {
            d[i] = 0;

            // 0이 아니어서 단독으로 해석 가능한 경우
            if (s[i - 1] != '0')
            {
                d[i] += d[i - 1];
            }

            // 앞글자와 조합해서 유효한 두 자리가 될 수 있는 경우
            if (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6')) 
            {
                d[i] += d[i - 2];
            }
        }

        return d[len];
    }
};

DP로 해결했다. 나에게는 조금 어려웠다. DP로 풀어야한다는 것 까지는 알겠는데, 논리가 헷갈려서 틀린 답안을 엄청 많이 냈다. 여러번 코드를 다듬고 주석을 추가해두었다. 다음에도 이 주석을 보고 다시 이해할 수 있기를!

이 포스트는 달레 스터디(3주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.