[LeetCode] 91. Decode Ways - 동적계획법(Dynamic Programming) JAVA

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

코드설명

동적계획법(Dynamic Programming) 을 활용합니다.

 

1글자로 짜르는 경우, 2글자로 짜르는 경우를 모두 완전탐색으로 탐색한뒤, 해당 구조가 최적 부분구조를 만족하므로 동적계획법을 활용해 중복연산을 피합니다.

 

leading zeros가 존재하는 문자인지, 1~26까지의 숫자로 가능한 알파벳인지의 여부를 확인하는 로직도 신경써서 구현합니다. 

 

이 문제의 경우, 저의 경우 leading zeros를 상당히 비효율적으로 구현하였습니다. 사실, 맨 앞에 '0'이 존재한다는 의미는, 무엇을 하든간에 0이 존재하므로 잘못된 경우입니다. 그렇기에 사실상 맨앞만 처리하면 되는 것이지요.

if(Str.length() >= 1 && str.charAt(0) == '0') return false;

코드

개선시킨 정답코드 2입니다.

isLeadingZero 판별로직이 훨씬 간단해졌습니다.

class Solution {
    int[] cache = new int[101];
    public int numDecodings(String s) {
        Arrays.fill(cache, -1);
        return DFS(0, s);
    }

    int DFS(int startIdx, String s){
        if(startIdx == s.length()){
            return 1;
        }
        if(cache[startIdx] != -1) return cache[startIdx];
        int ret = 0;
        //1글자로 짜르는 경우
        int endIdx = startIdx + 1;
        String str = s.substring(startIdx, endIdx);
        //해당 str이 leading zero 라면, 작동안됩니다.
        if( isNonLeadingZeroAndIsAlphabet(str) == true){
            ret += DFS(endIdx, s);
        }

        //2글자로 짜르는 경우
        endIdx = startIdx + 2;
        str = null;
        if(endIdx <= s.length())
            str = s.substring(startIdx, endIdx);
        if(str != null && isNonLeadingZeroAndIsAlphabet(str) == true){
            ret += DFS(endIdx, s);
        }
        return cache[startIdx] = ret;
    }

    boolean isNonLeadingZeroAndIsAlphabet(String str){
        if(str.length() >= 1 && str.charAt(0) == '0') return false;

        int idx = 0;
        int sum = 0;
        while(idx < str.length()){
            int num = str.charAt(idx) - '0';
            sum = sum * 10 + num;
            idx++;
        }
        if(sum < 0 || sum > 26) return false;
        return true;
    }

}

 

정답코드1입니다.

이 코드의 경우 isLeadingZero를 상당히 비효율적으로 작성했습니다.

class Solution {
    int[] cache = new int[101];
    public int numDecodings(String s) {
        Arrays.fill(cache, -1);
        return DFS(0, s);
    }

    int DFS(int startIdx, String s){
        if(startIdx == s.length()){
            return 1;
        }
        if(cache[startIdx] != -1) return cache[startIdx];
        int ret = 0;
        //1글자로 짜르는 경우
        int endIdx = startIdx + 1;
        String str = s.substring(startIdx, endIdx);
        //해당 str이 leading zero 라면, 작동안됩니다.
        if( isNonLeadingZeroAndIsAlphabet(str) == true){
            ret += DFS(endIdx, s);
        }

        //2글자로 짜르는 경우
        endIdx = startIdx + 2;
        str = null;
        if(endIdx <= s.length())
            str = s.substring(startIdx, endIdx);
        if(str != null && isNonLeadingZeroAndIsAlphabet(str) == true){
            ret += DFS(endIdx, s);
        }
        return cache[startIdx] = ret;
    }

    boolean isNonLeadingZeroAndIsAlphabet(String str){
        int idx = 0;
        boolean isLeadingZeroFound = false;
        int sum = 0;
        while(idx < str.length()){
            //만약 첫 숫자라면, 성공임.
            int num = str.charAt(idx) - '0';
            sum = sum * 10 + num;

            if(idx == 1)
                isLeadingZeroFound = true;
            if(isLeadingZeroFound == false && num == 0){
                return false;
            }
            idx++;
        }
        if(sum < 0 || sum > 26) return false;
        return true;
    }

}