Java Online Compiler
Example: Recursive Decoding Counter in Java
C
C++
C#
Java
Python
PHP
Main.java
STDIN
Run
// Recursive Decoding Counter public class Main { // Main function to initiate the recursive decoding process public static int countDecodingsRecursive(String s) { // Start the recursive helper function from the beginning of the string (index 0) return countDecodingsRecursiveHelper(s, 0); } // Helper function that performs the actual recursion private static int countDecodingsRecursiveHelper(String s, int index) { // Step 1: Base Case 1 - If we've reached the end of the string, it means we found one valid decoding. if (index == s.length()) { return 1; } // Step 2: Base Case 2 - If the current digit is '0', it cannot be decoded on its own. // It also cannot be part of a valid two-digit number (e.g., "01" is not 1, "00" is not valid). if (s.charAt(index) == '0') { return 0; } // Step 3: Count decodings by taking the current digit alone // Recursively call for the next position (index + 1) int count = countDecodingsRecursiveHelper(s, index + 1); // Step 4: Count decodings by taking the current digit and the next digit together // Check if there are at least two digits remaining and if they form a valid number (10-26) if (index + 1 < s.length()) { // Extract the two-digit number int twoDigitNum = Integer.parseInt(s.substring(index, index + 2)); // If the two-digit number is within the valid range [10, 26] if (twoDigitNum >= 10 && twoDigitNum <= 26) { // Add the decodings from taking two digits together count += countDecodingsRecursiveHelper(s, index + 2); } } // Step 5: Return the total count for the current subproblem return count; } public static void main(String[] args) { // Test cases for the recursive approach System.out.println("--- Recursive Approach ---"); System.out.println("Input: \"12\" | Possible decodings: " + countDecodingsRecursive("12")); // Expected: 2 (AB, L) System.out.println("Input: \"226\" | Possible decodings: " + countDecodingsRecursive("226")); // Expected: 3 (BBF, VF, BZ) System.out.println("Input: \"12345\" | Possible decodings: " + countDecodingsRecursive("12345")); // Expected: 3 (ABCDE, LCDE, AWDE) System.out.println("Input: \"10\" | Possible decodings: " + countDecodingsRecursive("10")); // Expected: 1 (J) System.out.println("Input: \"0\" | Possible decodings: " + countDecodingsRecursive("0")); // Expected: 0 System.out.println("Input: \"1\" | Possible decodings: " + countDecodingsRecursive("1")); // Expected: 1 System.out.println("Input: \"27\" | Possible decodings: " + countDecodingsRecursive("27")); // Expected: 1 (B7) } }
Output
Clear
ADVERTISEMENTS