Decode a string to all valid interpretations

Problem

Given a string s containing only digits, map the digits to letters ('A' -> 1, 'B' -> 2, ..., 'Z' -> 26) and return all valid interpretations of the encoded message.

Examples

Example 1

Input: s = "12"
Output: ["AB", "L"]
Explanation:
"12" can be interpreted as:
(1 2): 'AB'
(12): 'L'

Example 2

Input: s = "226"
Output: ["BBF", "BZ", "VF"]
Explanation:
"226" can be interpreted as:
(2 2 6): 'BBF'
(2 26): 'BZ'
(22 6): 'VF'

Example 3

Input: s = "0"
 Output: []
 Explanation:
 There is no valid interpretation for "0" because 0 does not map to any letter.

Example 4

Input: s = "10"
Output: ["J"]
Explanation:
"10" can be interpreted as:
(10): 'J'

Similar Problems

[Decode Ways](decode-ways) [Decode Ways II](decode-ways-ii)

Solution

Method 1 - Backtracking

Reasoning / Intuition

The problem is essentially about generating all combinations by picking single-digit ('1', '2', ..., '9') or valid two-digit numbers ('10', '11', ..., '26') that could be interpreted as letters.

A recursive backtracking approach is ideal:

1. Explore paths where digits are decoded as single letters.
2. Explore paths where two digits together form a valid letter.

Invalid combinations (e.g., digits starting with '0') are skipped.

Dynamic programming or iterative solutions could also be employed for optimisation, but recursion cleanly covers the problem due to its exploratory nature.

Approach

1. Use backtracking to recursively explore all valid interpretations.
2. Each recursive call decides whether to interpret:
   • One digit → Check if 1 <= int(s[i]) <= 9.
   • Two digits → Check if 10 <= int(s[i:i+2]) <= 26.
3. Build the result incrementally.
4. Add combinations to the result list when s is successfully parsed.

Code

C++

using namespace std;

class Solution {
public:
    vector<string> decodeMessage(string s) {
        vector<string> result;
        backtrack(s, 0, "", result);
        return result;
    }

private:
    void backtrack(string& s, int index, string current, vector<string>& result) {
        if (index == s.size()) {
            result.push_back(current);
            return;
        }

        // Single digit decoding
        if (index < s.size() && s[index] != '0') {
            char singleChar = 'A' + (s[index] - '1');
            backtrack(s, index + 1, current + singleChar, result);
        }

        // Two digit decoding
        if (index + 1 < s.size()) {
            int num = stoi(s.substr(index, 2));
            if (num >= 10 && num <= 26) {
                char doubleChar = 'A' + (num - 1);
                backtrack(s, index + 2, current + doubleChar, result);
            }
        }
    }
};

Java

y class Solution {
    public List<String> decodeMessage(String s) {
        List<String> result = new ArrayList<>();
        backtrack(s, 0, "", result);
        return result;
    }

    private void backtrack(String s, int index, String current, List<String> result) {
        if (index == s.length()) {
            result.add(current);
            return;
        }

        // Single digit decoding
        if (index < s.length() && s.charAt(index) != '0') {
            char singleChar = (char) ('A' + (s.charAt(index) - '1'));
            backtrack(s, index + 1, current + singleChar, result);
        }

        // Two digit decoding
        if (index + 1 < s.length()) {
            int num = Integer.parseInt(s.substring(index, index + 2));
            if (num >= 10 && num <= 26) {
                char doubleChar = (char) ('A' + (num - 1));
                backtrack(s, index + 2, current + doubleChar, result);
            }
        }
    }
}

Python

class Solution:
    def decodeMessage(self, s: str) -> list[str]:
        def backtrack(index, path):
            if index == len(s):
                result.append(path)
                return

            # Single digit decoding
            if index < len(s) and s[index] != '0':
                single_char = chr(int(s[index]) - 1 + ord('A'))
                backtrack(index + 1, path + single_char)

            # Two digit decoding
            if index + 1 < len(s):
                num = int(s[index:index+2])
                if 10 <= num <= 26:
                    double_char = chr(num - 1 + ord('A'))
                    backtrack(index + 2, path + double_char)

        result = []
        backtrack(0, "")
        return result

Complexity

• ⏰ Time complexity: O(2^n) → In the worst case, each character generates two recursive branches.
• 🧺 Space complexity: O(n) → Maximum depth of recursion stack is n.