Decode The Message - Leetcode Solution

Problem Statement:

You are given a message consisting of letters from A-Z encoded with numbers. Each letter is associated with a unique number from 1 to 26.

You have to decode the message and find all possible ways to decode the message.

Example:

Input: "12" Output: ["AB", "L"] Explanation: The message can be decoded as "AB" (1 2) or "L" (12).

Input: "226" Output: ["BZ", "VF", "BBF", "VZ", "WB"] Explanation: The message can be decoded as "BZ" (2 26), "VF" (22 6), "BBF" (2 2 6), "VZ" (22 26), or "WB" (23 6).

Solution:

Approach:

• The given problem can be solved using Dynamic Programming.
• We will create an array dp[] where dp[i] represents the number of ways to decode the substring s[0:i] (including i).
• Initially, the value of dp[0] will be 1 because an empty string can be decoded in one way.
• All the other values of dp[] will be initially set to 0.

Let’s follow the below steps to solve the problem using Dynamic Programming:

Step 1: Check if the first character of the string is ‘0’. If yes, return 0 because '0' can’t be decoded.

Step 2: Initialize dp[0]=1.

Step 3: Initialize dp[1] also to 1 if the first character of the string is anything other than '0'. Otherwise, set dp[1] to 0.

Step 4: Iterate over the remaining characters of the string (starting from index 2) and perform the following:

• If the current character s[i] is not '0', then we can combine it with the previous character s[i-1] to form a valid two-digit number (if the value of this number is less than or equal to 26).

• If we can form a two-digit number, then we can take either of the below paths:

• dp[i] = dp[i-1] + dp[i-2]

• dp[i] = dp[i-1]

• If we can’t form a two-digit number, then we can only take the path dp[i] = dp[i-1].

Step 5: Return the value of dp[n] (where n is the length of the input string).

Let’s understand the approach of the above solution with the help of an example:

Example:

Input: "226"

Step 1: Check if the first character of the string is ‘0’. s[0] != '0', so continue.

Step 2: Initialization: dp[0] = 1.

Step 3: Set dp[1] also to 1 (because the first character of the string is not '0').

Step 4: Loop: i=2, s[i]=6

• As the current character s[i] is not '0', so we can combine it with the previous character to form a valid two-digit number.

• The value of s[i-1]=2 and the value of the two-digit number formed is 26 which is less than or equal to 26.

• So, we can take either of the below paths:

• dp[i] = dp[i-1] + dp[i-2] = 1 + 1 = 2

• dp[i] = dp[i-1] = 1

• We can take the second path because the second path has a higher value.

Step 4: Loop: i=3, s[i]=2

• As the current character s[i] is not '0', so we can combine it with the previous character to form a valid two-digit number.
• The value of s[i-1]=6 and the value of the two-digit number formed is 62 which is greater than 26.
• So, we can only take the path dp[i] = dp[i-1] = 2.

Step 5: Return dp[3]=dp[n]=2.

Time Complexity:

The time complexity of the above algorithm is O(n) where n is the length of the input string.

Space Complexity:

The space complexity of the above algorithm is O(n) because we used an array of size n to store the auxiliary information.

Pseudo Code:

function decodeMessage(s: string): string[] { if (s[0] === "0") return [];

let n = s.length;

let dp = new Array(n).fill(0);
dp[0] = 1;
dp[1] = s[1] === "0" ? 0 : 1;

for (let i = 2; i < n; i++) {
    if (s[i] !== "0") 
        dp[i] += dp[i-1];

    let twoDigitNumber = Number(s[i-1] + s[i]);
    if (twoDigitNumber >= 10 && twoDigitNumber <= 26) 
        dp[i] += dp[i-2];
}

let result = [];

dfs(s, 0, "", dp, result);

return result;

}

function dfs(s: string, index: number, sb: string, dp: number[], result: string[]): void { let n = s.length;

if (index === n) {
    result.push(sb)
    return;
}

if (s[index] === "0") return;

let num = 0;
for (let i = index; i < n; i++) {
    num = num * 10 + Number(s[i]);
    if (num > 26) break;

    dfs(s, i+1, sb + String.fromCharCode(num+64), dp, result);
}

}

Explanation:

• We first check if the first character of the string is '0'. If yes, we return an empty array (because '0' can't be decoded).
• We then initialize a dp[] array of size n (where n is the length of the input string). We set dp[0] to 1 because an empty string can be decoded in one way. We set dp[1] to 1 also if the first character of the string is anything other than 0. Otherwise, we set dp[1] to 0.
• We then loop through the remaining characters of the string (starting from index 2) and perform step 4. In step 4, we check if the current character is not '0'. If yes, we combine it with the previous character to form a valid two-digit number (if the value of this number is less than or equal to 26). If we can form a two-digit number, then we can take either of the two paths. We store the value in dp[i]. We then go to the next iteration.
• After we finish the loop, we create an empty result array and call the dfs() function to find all possible ways to decode the message. We pass the index, the dp[] array, and an empty string to the dfs() function to get all the possible decodings of the message. We then return the result array.

Summary:

In this problem, we saw how to decode a message having a combination of letters and numbers and find all possible ways to decode the message. We used Dynamic Programming to find the number of ways to decode the message. We then used Depth First Search to get all the possible decodings of the message.

1