1. class Solution {
  2.     /**
  3.     Explanation
  4.     numDecodings(String s) — entry point.
  5.     Calls decodeCount starting from index 0.
  6.     decodeCount(String s, int index) — recursive helper.
  7.         - Returns the number of ways to decode the substring starting at index.
  8.         - Base case: index == s.length() → return 1.
  9.         - If the current character is '0' → return 0 (invalid).
  10.         - Try 1-digit decoding → recurse index + 1.
  11.         - Try 2-digit decoding if 10 ≤ number ≤ 26 → recurse index + 2.
  12.     Return total count.
  13.     example:
  14.     decodeCount("1012", 0)
  15.     ├─ 1-digit: "1" → invalid → 0 ways
  16.     ├─ 2-digit: "10" → valid → decodeCount("12", 2)
  17.         ├─ 1-digit: "1" → decodeCount("2", 3) → 1 way
  18.         └─ 2-digit: "12" → decodeCount("", 4) → 1 way
  19.     Total = 0 + (1 + 1) = 2 ways
  20.     */
  21.     public int numDecodings(String s) {
  22.         int n = s.length();
  23.         return decodeCount(s, 0, n);
  24.     }
  25.  
  26.     public int decodeCount(String s, int index, int n)
  27.     {
  28.         if(index == n)
  29.             return 1;
  30.  
  31.         // If current digit is '0', cannot decode → 0 ways
  32.         if(s.charAt(index) == '0')
  33.             return 0;
  34.  
  35.         // Take only 1 digit
  36.         int count = decodeCount(s, index+1, n);
  37.  
  38.         // Take 2 digits if valid (10–26)
  39.         if(index+1 < n)
  40.         {
  41.             int num = Integer.parseInt(s.substring(index, index+2));
  42.             // valid number that lies in alphabet range
  43.             if(num >= 10 && num <=26)
  44.             {
  45.                 count += decodeCount(s, index+2, n);
  46.             }
  47.         }
  48.         return count;
  49.     }
  50. }