leetcode - decode ways II(kotlin)

level - hard

[문제 내용]
해당 encode 된 문자열을 decode 할 수 있는 방법이 몇가지인지 구하기..
'A'-'Z' -> '1'-'26'
'*' -> '1'-'9'

[example 1]

Input: s = "*"
Output: 9
Explanation: The encoded message can represent any of the encoded messages "1", "2", "3", "4", "5", "6", "7", "8", or "9".
Each of these can be decoded to the strings "A", "B", "C", "D", "E", "F", "G", "H", and "I" respectively.
Hence, there are a total of 9 ways to decode "*".

[example 2]

Input: s = "1*"
Output: 18
Explanation: The encoded message can represent any of the encoded messages "11", "12", "13", "14", "15", "16", "17", "18", or "19".
Each of these encoded messages have 2 ways to be decoded (e.g. "11" can be decoded to "AA" or "K").
Hence, there are a total of 9 * 2 = 18 ways to decode "1*".

[example 3]

Input: s = "2*"
Output: 15
Explanation: The encoded message can represent any of the encoded messages "21", "22", "23", "24", "25", "26", "27", "28", or "29".
"21", "22", "23", "24", "25", and "26" have 2 ways of being decoded, but "27", "28", and "29" only have 1 way.
Hence, there are a total of (6 * 2) + (3 * 1) = 12 + 3 = 15 ways to decode "2*".

[해결 방법]
문제를 읽자마자 감이 왔다 이것은 dp로 풀지 않으면 시간초과가 날것이라고..
하.. dp는 느므 으렵다..
결국 다른 사람의 풀이를 보고 알았다..
그래도 양심상 decode ways2 말고 decode ways1 보고 풀었댜..

너무 졸린상태에서 글을 쓰는거라..
잘 설명할 자신이 없다.

dp의 크기는 주어진 문자열의 크기만큼으로 할당한다.
해당 dp의 첫번째 값으로는 해당 문자열의 첫번째 문자에 따라 결정한다.
0이면 혼자 올 수 없으므로 0
*이면 9개가 올 수 있으니까 9
나머지는 1

위와 같이 처음을 설정한 후
해당 문자열이 이제 위와 같이 올수 있는 경우의 수를 각각 구해서
앞의 dp값과 곱해서 더해주면 된다..

생각보다 엄청 어렵진 않았는데
항상 그 처음을 스타트하는게 어렵다.

그리고 한가지 팁이라면
항상 modulo 10^9 + 7 을 하라고 하면
int보다 범위가 큰값이 들어온다는거니..
long 타입으로 설정하도록 하자..
항상 읽고도 아무생각없이 int로 설정하고
왜? 라고 하면서 이상한데서 헤맨다..

class Solution {
    fun numDecodings(s: String): Int {
        val dp = LongArray(s.length)
        when(s[0]) {
            '0' -> dp[0] = 0
            '*' -> dp[0] = 9
            else -> dp[0] = 1
        }

        for(i in 1 until s.length) {
            if(s[i] == '*') {
                dp[i] = (dp[i] + dp[i-1]*9) % 1000000007

                if(s[i-1] == '*') {
                    dp[i] = (dp[i] + if(i>=2) dp[i-2] * 15 else 15) % 1000000007
                } else {
                    when(s[i-1]) {
                        '1' -> dp[i] = (dp[i] + if(i>=2) dp[i-2]*9 else 9) % 1000000007
                        '2' -> dp[i] = (dp[i] + if(i>=2) dp[i-2]*6 else 6) % 1000000007
                    }
                }
            } else {
                val one = s[i] - '0'
                if (one != 0) {
                    dp[i] += dp[i - 1]
                }

                if(s[i-1] == '*') {
                    if(one in 7..9) {
                        dp[i] = (dp[i] + if(i>=2) dp[i-2] else 1) % 1000000007
                    } else {
                        dp[i] = (dp[i] + if(i>=2) dp[i-2]*2 else 2) % 1000000007
                    }
                } else {
                    val ten = (s[i - 1] - '0') * 10 + one
                    if (ten in 10..26) {
                        dp[i] =  (dp[i] + if (i >= 2) dp[i - 2] else 1) % 1000000007
                    }
                }
            }
        }

        return dp[s.length-1].toInt()
    }
}