AI Mobile CodersJoin
← Coding round practice

Decode Ways

MediumDynamic Programming

The problem

Count how many ways a digit string can be decoded into letters, where A=1 ... Z=26. Bottom-up DP.

Sample input

226

Sample output

3
Show the solution · 8 languages
fun numDecodings(s: String): Int {
    if (s.isEmpty() || s[0] == '0') return 0
    val n = s.length
    val dp = IntArray(n + 1)
    dp[0] = 1
    dp[1] = 1
    for (i in 2..n) {
        if (s[i - 1] != '0') dp[i] += dp[i - 1]
        val two = s.substring(i - 2, i).toInt()
        if (two in 10..26) dp[i] += dp[i - 2]
    }
    return dp[n]
}

fun main() {
    println(numDecodings("226"))
}