coderz.py

Problem Statement (Asked By Facebook)

Given the mapping a = 1, b = 2, …, z = 26, and an encoded message, count the number of possible ways to decode it.

For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'.

You can assume that the messages are valid. For instance, '001' is not allowed.

Problem link: https://leetcode.com/problems/decode-ways/

Disclaimer: Try solving the problem on your own first! Use this solution only as a reference to learn and improve.

---

Solution:

This problem is well-suited for a recursive approach. Let’s break it down by defining a recurrence to solve it. Here are some test cases to understand the logic:

1. An empty string ("") is the base case, and it should return 1 since there’s one way to decode it: doing nothing.
2. A string like "1" should return 1, as it can only be decoded as "a".
3. "11" should return 2 since it can be decoded as "aa" or "k".
4. "111" should return 3:
   • "a" + "k"
   • "k" + "a"
   • "a" + "a" + "a".
5. Strings like "011" or "602" should return 0 because no letter starts with 0.

The recursive structure is as follows:

• If the string starts with 0, there’s no valid decoding.
• If the string length is 1 or less, there’s exactly 1 way to decode it.
• If the first two digits form a number ≤ 26, we recursively calculate the number of ways to decode assuming we treat it as a single letter.
• Additionally, we calculate the ways to decode by treating only the first digit as a letter.

Here’s the recursive solution:

Approach 1:

Recursive Approach (Inefficient, O(2^n)):

public class DecodeWays {
    public static int numEncodings(String s) {
        if (s.startsWith("0")) {
            return 0;
        } else if (s.length() <= 1) {
            return 1;
        }

        int total = 0;

        if (Integer.parseInt(s.substring(0, 2)) <= 26) {
            total += numEncodings(s.substring(2));
        }

        total += numEncodings(s.substring(1));
        return total;
    }

    public static void main(String[] args) {
        System.out.println(numEncodings("111")); // Output: 3
        System.out.println(numEncodings("011")); // Output: 0
    }
}

1. Recursive Approach:

• Directly breaks the problem into subproblems by trying two cases: decoding one character or two.
• Inefficient due to repeated calculations for overlapping subproblems.

Approach 2:

Optimized Dynamic Programming Approach (O(n)):

Instead of making redundant recursive calls, we can use a bottom-up dynamic programming approach. We calculate the number of ways to decode the string from the end to the beginning and store intermediate results in a cache.

import java.util.HashMap;
import java.util.Map;

public class DecodeWays {
    public static int numEncodings(String s) {
        if (s.isEmpty() || s.startsWith("0")) {
            return 0;
        }

        Map<Integer, Integer> cache = new HashMap<>();
        cache.put(s.length(), 1); // Base case: empty string has 1 way to decode

        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '0') {
                cache.put(i, 0);
            } else {
                cache.put(i, cache.get(i + 1));
                if (i + 1 < s.length() &amp;&amp; Integer.parseInt(s.substring(i, i + 2)) <= 26) {
                    cache.put(i, cache.get(i) + cache.get(i + 2));
                }
            }
        }
        return cache.get(0);
    }

    public static void main(String[] args) {
        System.out.println(numEncodings("111")); // Output: 3
        System.out.println(numEncodings("011")); // Output: 0
        System.out.println(numEncodings("226")); // Output: 3
    }
}

2. Dynamic Programming Approach:

• Stores intermediate results in a cache (map) to avoid recalculating.
• Traverses the string from right to left, calculating the number of ways to decode each substring.

Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n) for the cache.

---

Did this solution help you understand the concept better? Let me know your thoughts in the comments below! Don’t forget to follow us on Instagram @coderz.py for more DSA tips and solutions to ace your coding interviews.