Decode Ways

shriyanshi24jindal

Mar 28th, 2026

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 7.38 KB | None | 0 0

copy raw download clone embed print report

class Solution {
/**
Explanation
numDecodings(String s) — entry point.
Calls decodeCount starting from index 0.
decodeCount(String s, int index) — recursive helper.
- Returns the number of ways to decode the substring starting at index.
- Base case: index == s.length() → return 1.
- If the current character is '0' → return 0 (invalid).
- Try 1-digit decoding → recurse index + 1.
- Try 2-digit decoding if 10 ≤ number ≤ 26 → recurse index + 2.
Return total count.
example:
decodeCount("1012", 0)
├─ 1-digit: "1" → invalid → 0 ways
├─ 2-digit: "10" → valid → decodeCount("12", 2)
├─ 1-digit: "1" → decodeCount("2", 3) → 1 way
└─ 2-digit: "12" → decodeCount("", 4) → 1 way
Total = 0 + (1 + 1) = 2 ways
*/
public int numDecodings(String s) {
int n = s.length();
return decodeCount(s, 0, n);
}
public int decodeCount(String s, int index, int n)
{
if(index == n)
return 1;
// If current digit is '0', cannot decode → 0 ways
if(s.charAt(index) == '0')
return 0;
// Take only 1 digit
int count = decodeCount(s, index+1, n);
// Take 2 digits if valid (10–26)
if(index+1 < n)
{
int num = Integer.parseInt(s.substring(index, index+2));
// valid number that lies in alphabet range
if(num >= 10 && num <=26)
{
count += decodeCount(s, index+2, n);
}
}
return count;
}
}

RAW Paste Data Copied

class Solution {
    /**
    Explanation
    numDecodings(String s) — entry point.
    Calls decodeCount starting from index 0.
    decodeCount(String s, int index) — recursive helper.
        - Returns the number of ways to decode the substring starting at index.
        - Base case: index == s.length() → return 1.
        - If the current character is '0' → return 0 (invalid).
        - Try 1-digit decoding → recurse index + 1.
        - Try 2-digit decoding if 10 ≤ number ≤ 26 → recurse index + 2.
    Return total count.
    example:
    decodeCount("1012", 0)
    ├─ 1-digit: "1" → invalid → 0 ways
    ├─ 2-digit: "10" → valid → decodeCount("12", 2)
        ├─ 1-digit: "1" → decodeCount("2", 3) → 1 way
        └─ 2-digit: "12" → decodeCount("", 4) → 1 way
    Total = 0 + (1 + 1) = 2 ways
    */
    public int numDecodings(String s) {
        int n = s.length();
        return decodeCount(s, 0, n);
    }

public int decodeCount(String s, int index, int n)
    {
        if(index == n)
            return 1;
        
        // If current digit is '0', cannot decode → 0 ways
        if(s.charAt(index) == '0')
            return 0;
        
        // Take only 1 digit
        int count = decodeCount(s, index+1, n);

// Take 2 digits if valid (10–26)
        if(index+1 < n)
        {
            int num = Integer.parseInt(s.substring(index, index+2));
            // valid number that lies in alphabet range
            if(num >= 10 && num <=26)
            {
                count += decodeCount(s, index+2, n);
            }
        }
        return count;
    }
}