Decoding no of ways and printing each decode message

[Saumyojit]

Question in short:
print The encoded message in how many ways can it be decoded and print each decoded message of evry encoded message
1 represents A ...26 is z and

04 or 06 ... is invalid

27 , 28 INVALID as there is no Alphabhet above 26

input : 243
eg:

2 4 3 output BDC

24 3 output will be XC



so 2 ways


Input : 22415
Only one single and other will be in pair ( only for odd length string)

Single is first 2


other pair 24, 15
then,
Output :B X O

Or it can be like this



input: 22415
Single is 2nd position '4'

& others are in Pair

pair is 22,15

Output :
V D O




I have to get every possible combinations .

See i thought of in this way

First i will take input of the string ,

then i will divide by i which will start from 2 and end at length of the String . Then, I will divide the string by each value of i .

suppose the string is 8 bit long " 22423146"

'i' tells us in how many parts i am dividing the original input

when i completely divides length , then the String is divided in equal parts



suppose when i=2 then the string is divided to 2242 3146 . This is Invalid.

i=4 (4 parts) , then i get this 22 42 31 46 which is a valid Combination.

when i =8 , then I will get only single : 2 2 4 2 3 1 4 6







BUt when i is not a divisor of length '8' (i=3,5,7) then

Observe that space in between parts is always one less than the no of parts

i=5 (5 parts),

it can be 22 4 2 31 46 ( invalid due to 31 and 46)

or if i shift the space in between 2 and 3 to between 3 and 1 .
then i will get a unique arrangement 22 4 23 14 6 (valid)



Now i can rearrange the spaces anyway in between the parts and place them in between two characters to give arise to a new combination, PROVIDED that two spaces don't sit side by side .

This is what i told is the LOGIC but how will i implement in the code in C or JAVA.

The checking part whether it is invalid or valid (Greater than 26 and any character double or single starting with Zero or not ) and matching the characters single or Double to Corresponding Alphabhet ---- that i will do it .

I also know how to extract characters by using charAt(i) ; and I also Know Recursion .

But how to introduce space and how to drift the space from its initial postion to another new position to get another new combination when (length % i !=0) , and how will I divide the string to ' i ' Parts , How to put all of these together . IT's an uphill task for me .

 

[CodeMonkeyJ]

This one's a doozy! It'll definitely need recursion to make it simpler. Give me a bit...

 

[CodeMonkeyJ]

Alright, I've got it written in (probably inefficient) C++. I can post it, but if you need it in Java or C, the pseudo-code is, generally:

list_of_strings decode_string(string, index):
    if string[index] == '0':
        return []
        
    if index == string.length() - 1:
        return decode_characters(string.substr(index, 1))
    
    return_list = []
    this_character = decode_characters(string.substr(index, 1))
    for (str : decode_string(string, index+1)):
        return_list += this_character + str
        
    if index < string.length() - 1:
        if string[index] == '1' or (string[index] == '2' and string[index+1] <= '6'):
            this_character = decode_characters(string.substr(index, 2))
            for (str : decode_string(string, index+2)):
                return_list += this_character + str
                
    return return_list

decode_characters would take a numeric string for one character and decode it (i.e., "1" == "a", "26" == "z"). So, you decode your current index, if possible (check for zero, which is invalid), and prepend it to every iteration found after that, recursively. Then, if it looks like this index and the next one make another valid number, prepend THAT to every iteration found after that combination.