Total Decoding Messages

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Count ways to decode digit string (1=A..26=Z). DP with one and two digit choices.

Algorithm

1dp[i] = ways to decode s[0..i-1]. dp[i] += dp[i-1] if s[i-1] valid single. dp[i] += dp[i-2] if s[i-2..i-1] in 10..26.

Common Pitfalls

•Same as LC 91. Handle leading zeros: "0" alone is invalid. "10","20" are valid two-digit decodings.

Total Decoding Messages.java

Java

// Approach: DP. dp[i] = ways to decode s[0..i-1]. One-char decode + two-char decode transitions.
// Time: O(n) Space: O(1)
import java.util.*;

class Solution {
    int[] dp;

    public int countWays(String digits) {
        dp = new int[digits.length() + 1];
        Arrays.fill(dp, -1);
        int ans = countDecodes(0, digits);
        return ans;
    }

    private int countDecodes(int i, String digits) {
        if (i >= digits.length())
            return 1;
        else if (digits.charAt(i) == '0')
            return 0;
        else if (dp[i] != -1)
            return dp[i];

        dp[i] = countDecodes(i + 1, digits);
        int digit1 = digits.charAt(i) - '0';
        if (i + 1 < digits.length() && (digit1 == 1 || (digit1 == 2 && digits.charAt(i + 1) <= '6')))
            dp[i] += countDecodes(i + 2, digits);

        return dp[i];
    }
}

Was this solution helpful?