Title:

Decode Ways

Specification:

A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.

Examples:

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Initial Code and Signature:

``` public interface Decoder { public int numDecodings(String s); } ```

Algorithm:

Main Idea:
In some cases F (n) = F (n + 1) + F (n + 2); if char [n] and char [n+1] >= 1 and <= 26.
In some cases F (n) = F (n + 1); if char [n] >= 3 or if char [n] and char [ n+1 ] >= 27.
In some cases F (n) = F (n + 2); if char [n] and char [n+1] = 10 or 20;
In one case F (n) = 0; if char [n] = 0;
1. Consider an array of integer, called number of decodings, having the length of the given string.
2. Start from the end of the given string, and scan the last character.
3. If the number that the last char represents is between 1 and 9 then set the related cell in the number of decodings to 1.
4. else if the number is zero then set the related cell to 0.
5. Move to the previous char.
1. If the number that the current char represents is greater or equal to three or if the current char is 2 and the next char is 7 or higher then number of decodings [i] = number of decodings [ i+1 ], since there is only one way to decode this char, and that way is to remove the current char alone.
2. Else if the number the current char represents is 0, then number of decodings [i] = 0, since there is no valid decoding for this char.
3. Else if the number that the current char and the next char represent is 10 or is 20, then number of decodings [i] = number of decodings [ i+2 ], since there is only one way to decode the current char and that way is to decode it together with the next char.
4. Else if the number the current char and the next char represent is between 1 and 26, then number of decodings [i] = number of decodings [ i+1 ] + number of decodings [ i+2 ], since there are two ways to decode the current char.
1. to decode the current char alone and go to the next char , or
2. to decode the current char with the next char, and then go to the char after the next char.
6. Go to 5- and continue until all of the string is scanned.
7. Return number of decodings .

Run-Time Complexity Analysis

GitHub Project:

Code:

``` /** * * @author Mahsa Sadi * * @since 2020 - 06 - 17 * * License: Creative Commons * * Copyright by Mahsa Sadi * */ public class DecoderS3 implements Decoder { /** * Problem: Decode Ways * * * Description: * * A message containing letters from A-Z is being encoded to numbers using the following mapping: * 'A' -> 1 * 'B' -> 2 * ... * 'Z' -> 26 * * Given a non-empty string containing only digits, determine the total number of ways to decode it. * * * * * Solution: * * Main Idea: * In some cases F (n) = F (n + 1) + F (n + 2); if char [n] and char [n+1] >= 1 and <= 26. * In some cases F (n) = F (n + 1); if char [n] >= 3 or if char [n] and char [ n+1 ] >= 27 * In some cases F (n) = F (n + 2); if char [n] and char [n+1] = 10 or 20; * In one case F (n) = 0; if char [n] = 0; * * 1- Consider an array of integer, called number of decodings, having the length of the given string. * * 2- Start from the end of the given string, and scan the last character. * * 3- If the number that the last char represents is between 1 and 9 then set the related cell in the number of decodings to 1. * * 4- else if the number is zero then set the related cell to 0. * * 5- Move to the previous char. * * 6- If the number that the current char represents is greater or equal to three or if the current char is 2 and the next char is 7 or higher then * number of decodings [i] = number of decodings [ i+1 ], since there is only one way to decode this char, and that way is to remove the current char alone. * * 7- Else if the number the current char represents is 0, then * number of decodings [i] = 0, since there is no valid decoding for this char. * * * 8- Else if the number that the current char and the next char represent is 10 or is 20, then * number of decodings [i] = number of decodings [ i+2 ], since there is only one way to decode the current char and that way is to decode it together with the next char. * * 9- Else if the number the current char and the next char represent is between 1 and 26, then * number of decodings [i] = number of decodings [ i+1 ] + number of decodings [ i+2 ], since there are two ways to decode the current char * 1- to decode the current char alone and go to the next char , or * 2- to decode the current char with the next char, and then go to the char after the next char. * * 10- Go to 5- and continue until all of the string is scanned. * * 11- Return number of decodings ; * */ @Override public int numDecodings(String s) { int [] numberOfDecodings = new int [s.length()]; int currentNum, nextNum; currentNum = Integer.parseInt(s.charAt(s.length() - 1 )+""); if ( currentNum != 0 ) numberOfDecodings [s.length() - 1 ] = 1; else numberOfDecodings [s.length() - 1 ] = 0; for (int i = s.length() - 2; i >= 0; i--) { nextNum = currentNum; currentNum = Integer.parseInt(s.charAt(i) +""); if (currentNum == 0) numberOfDecodings [i] = 0; else { if ( currentNum >= 3 || (currentNum == 2 && nextNum >= 7 ) ) numberOfDecodings [i] = numberOfDecodings [i + 1]; else if ( i + 2 <= s.length() - 1 && ( ( currentNum == 1 || currentNum == 2 ) && nextNum == 0) ) numberOfDecodings [i] = numberOfDecodings [i + 2]; else { if ( i + 2 <= s.length() - 1) numberOfDecodings [i] = numberOfDecodings [i + 1] + numberOfDecodings [i + 2]; else { if ( ( currentNum == 1 || currentNum == 2 ) && nextNum == 0) numberOfDecodings [i] = 1; else numberOfDecodings [i] = 2; } } } } return numberOfDecodings ; } } ```