Example: Tabulated Decoding Counter in Java

// Tabulated Decoding Counter
public class Main {

    // Main function to initiate the tabulated dynamic programming decoding process
    public static int countDecodingsTabulation(String s) {
        int n = s.length();
        // Step 1: Handle edge case for an empty string. An empty string has 1 way to decode (empty sequence).
        if (n == 0) return 1;

        // Step 2: Create a DP array. dp[i] will store the number of ways to decode the substring s[i...n-1].
        // Size is n + 1 to handle index n (representing an empty suffix).
        int[] dp = new int[n + 1];

        // Step 3: Initialize base cases for the DP table.
        // dp[n] represents the number of ways to decode an empty string (suffix starting at index n).
        // There is one way to decode an empty string: by doing nothing.
        dp[n] = 1;

        // dp[n-1] represents the number of ways to decode the last character.
        // If the last character is '0', it cannot be decoded (0 ways).
        // Otherwise (1-9), it can be decoded in one way (1 way).
        dp[n - 1] = (s.charAt(n - 1) == '0') ? 0 : 1;

        // Step 4: Fill the DP table from right to left (from n-2 down to 0)
        // This ensures that dp[i+1] and dp[i+2] are already computed when we calculate dp[i].
        for (int i = n - 2; i >= 0; i--) {
            // If the current digit is '0', it cannot be decoded. So, dp[i] is 0.
            if (s.charAt(i) == '0') {
                dp[i] = 0;
                continue; // Move to the next iteration
            }

            // Way 1: Decode the current digit alone.
            // This contributes dp[i+1] ways (decodings of the rest of the string from i+1).
            // This is always possible if s.charAt(i) is not '0'.
            dp[i] = dp[i + 1];

            // Way 2: Decode the current digit and the next digit together.
            // Check if s[i]s[i+1] forms a valid two-digit number (10-26).
            int twoDigitNum = Integer.parseInt(s.substring(i, i + 2));
            if (twoDigitNum >= 10 && twoDigitNum <= 26) {
                // If valid, add dp[i+2] ways (decodings of the rest of the string from i+2).
                dp[i] += dp[i + 2];
            }
        }

        // Step 5: The result for the entire string s[0...n-1] is stored in dp[0].
        return dp[0];
    }

    public static void main(String[] args) {
        // Test cases for the tabulated approach
        System.out.println("\n--- Tabulated Dynamic Programming Approach ---");
        System.out.println("Input: \"12\" | Possible decodings: " + countDecodingsTabulation("12"));
        System.out.println("Input: \"226\" | Possible decodings: " + countDecodingsTabulation("226"));
        System.out.println("Input: \"12345\" | Possible decodings: " + countDecodingsTabulation("12345"));
        System.out.println("Input: \"10\" | Possible decodings: " + countDecodingsTabulation("10"));
        System.out.println("Input: \"0\" | Possible decodings: " + countDecodingsTabulation("0"));
        System.out.println("Input: \"1\" | Possible decodings: " + countDecodingsTabulation("1"));
        System.out.println("Input: \"27\" | Possible decodings: " + countDecodingsTabulation("27"));
    }
}