27143
« Last post by mouser on April 13, 2007, 02:15 AM »
Interesting problem.
ok assuming you are not trying to do anything clever like reject possibilities that dont map to english text, and assuming you dont have to worry about stack overflows on too many recursive calls (which you will have to worry about if you really want to implement this on long strings), it should be pretty straightforward.
some pseudocode:
you could start with a function like
DecodeRemainder(string textsofar, string remainingmorsecode)
{
if (remainingmorsecode=="")
{
print textsofar;
return;
}
for (int i=1;i<=7;++i)
{
letter = DecodeMorseCodeUsingNChars(remainingmorsecode,i);
if (letter!=NULL)
{
DecodeRemainder(textsofar + letter, remainingmorsecode.substr(i,len(remainingmorsecode-i) );
}
}
}
now keep in mind i dont quite recommend this approach - it's just a theoretical recursive solution off the top of my head which i think will work.
a better solution that wouldnt kill the stack with recursive calls could simply do something like this:
for each position in the morse code string, keep track of 7 pairs of [Lettter, morsecoderemainder position].
then you could much more easily iterate through every possible output by basically walking through the index of branch decisions from
1,1,1,1,1,1,1,1,1 (vector length is the length of the morsecodestring) to
1,1,1,1,1,1,1,1,7 to
...
7,7,7,7,7,7,7,7,7
something like that, if you follow my meaning, stopping when you run out of characters.