Example: Memoized Decoding Counter in Java

// Memoized Decoding Counter
import java.util.Arrays; // Needed for Arrays.fill()

public class Main {

    // Main function to initiate the memoized dynamic programming decoding process
    public static int countDecodingsMemoized(String s) {
        // Create a memoization array to store results of subproblems.
        // Size is s.length() + 1 to include states for index s.length().
        int[] memo = new int[s.length() + 1];
        // Initialize memoization array with -1 to indicate uncomputed states
        Arrays.fill(memo, -1);
        // Start the memoized helper function from the beginning of the string (index 0)
        return countDecodingsMemoizedHelper(s, 0, memo);
    }

    // Helper function that performs the memoized recursion
    private static int countDecodingsMemoizedHelper(String s, int index, int[] memo) {
        // Step 1: Base Case 1 - If we've reached the end of the string, one valid decoding found.
        if (index == s.length()) {
            return 1;
        }

        // Step 2: Base Case 2 - If the current digit is '0', it cannot be decoded.
        if (s.charAt(index) == '0') {
            return 0;
        }

        // Step 3: Check if the result for this index has already been computed and stored
        if (memo[index] != -1) {
            return memo[index]; // Return the stored result
        }

        // Step 4: Count decodings by taking the current digit alone
        int count = countDecodingsMemoizedHelper(s, index + 1, memo);

        // Step 5: Count decodings by taking the current digit and the next digit together
        if (index + 1 < s.length()) {
            int twoDigitNum = Integer.parseInt(s.substring(index, index + 2));
            if (twoDigitNum >= 10 && twoDigitNum <= 26) {
                count += countDecodingsMemoizedHelper(s, index + 2, memo);
            }
        }

        // Step 6: Store the computed result for the current index before returning
        memo[index] = count;
        return count;
    }

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