Untitled

class Solution {
    public int numDecodings(String s) {
        if (s == null || s.isEmpty()) return 0;
        int n = s.length();
        Integer[] memo = new Integer[n];
        return decodeWays(s, 0, memo);
    }
    
    private int decodeWays(String s, int index, Integer[] memo) {
        // Base case: If we've decoded the entire string, count as 1 way.
        if (index == s.length()) return 1;
        
        // If the current character is '0', it cannot be decoded.
        if (s.charAt(index) == '0') return 0;
        
        // Check memoized results.
        if (memo[index] != null) return memo[index];
        
        // Decode single character.
        int ways = decodeWays(s, index + 1, memo);
        
        // Decode two characters if valid.
        if (index + 1 < s.length()) {
            int twoDigit = Integer.parseInt(s.substring(index, index + 2));
            if (twoDigit >= 10 && twoDigit <= 26) {
                ways += decodeWays(s, index + 2, memo);
            }
        }
        
        // Memoize and return the result.
        memo[index] = ways;
        return ways;
    }
}