Given A morse String eg. aet = ".- . -" if the spaces are removed it will become an ambiguous morse string ".-.-" which can represent "aet","eta","ent","etet" etc.
the problem is to find the no.of words that the morse string without spaces can represent irrespective of the meaning of the words. The constraint is that the new word which is formed should be the same size of the input i.e "aet" = "ent" and other words like "etet" should be discarded.
i implemented a recursive solution for some reason it is not working. below is my code and thinking of converting this to DP approach to increase time efficiency. Can some one help to point out the mistake in the below code and is DP a right approach to follow for this problem? Thanks in advance!!
EDIT 1 :- The program gives me an output but not the correct one. for ex. for the morse String representing aet = ".- . -" if given without any spaces to the program ".-.-" it should give an out put "3" i.e 3 words can be formed that is of the same size as the input including the input "aet","eta","ent" but it gives me an output "1". I think there is some thing wrong with the recursive calls.
The approach used here is to simply cut the morse string in a place where first valid morse code is encountered and the repeat the process with the rest of the string untill 3 such valid morse code are found and check whether whole morse string is consumed. if consumed increment the word count and repeat the process for different values of substring size(end variable in the below code).
I hope this helps!!.Tried my best to explain as clearly as I could.
import java.util.*;
import java.io.*;
import java.math.*;
import java.text.*;
public class MorseCode2 {
static Map<String,String> morseCode;
static Map<String,String> morseCode2;
static int count = 0;
public static void main(String args[]){
String[] alpha = {"a","b","c","d","e","f","g","h","i","j","k",
"l","m","n","o","p","q","r","s","t","u","v",
"w","x","y","z"};
String[] morse = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",
".--","-..-","-.--","--.."};
morseCode = new HashMap<String,String>();
morseCode2 = new HashMap<String,String>();
for(int i = 0;i<26;i++){
morseCode.put(morse[i],alpha[i]);
}
for(int i = 0;i<26;i++){
morseCode2.put(alpha[i],morse[i]);
}
Scanner in = new Scanner(System.in);
String input = in.next();
String morseString = "";
for(int j = 0; j< input.length(); j++){
morseString += morseCode2.get(input.charAt(j)+"");
}
countPossibleWord(morseString,input.length(),0,1,0);
System.out.println(count);
in.close();
}
public static void countPossibleWord(String s,int inputSize,int start,int end,int tempCount){
if(start >= s.length() || end > s.length()){
return;
}
if(tempCount>inputSize){
return;
}
String sub = s.substring(start, end);
if(sub.length()>4){
return;
}
if(morseCode.get(sub)!=null){
tempCount++;
countPossibleWord(s,inputSize,end,end+1,tempCount);
}
else{
countPossibleWord(s,inputSize,start,end+1,tempCount);
}
if(tempCount == inputSize && end == s.length()){
count++;
}
countPossibleWord(s,inputSize,start,end+1,0);
}
}
EDIT 2 :- Thank you all for your Responses and Extremely sorry for the confusing code, will surely try to improve on writing neat and clear code. learnt a lot from your replies!!
And i also some how made the code work, the problem was I passed wrong argument which changed the state of the recursive calls. Instead of passing "tempCount-1" for the last argument in the last function call in the method "countPossibleWord" i passed "0" this altered the state. found this after running through the code manually for larger inputs. below is the corrected method
public static void countPossibleWord(String s,int inputSize,int start,int end,int tempCount){
if(start >= s.length() || end > s.length()){
return;
}
if(tempCount>inputSize){
return;
}
String sub = s.substring(start, end);
if(sub.length()>4){
return;
}
if(morseCode.get(sub)!=null){
tempCount++;
countPossibleWord(s,inputSize,end,end+1,tempCount);
}
else{
countPossibleWord(s,inputSize,start,end+1,tempCount);
}
if(tempCount == inputSize && end == s.length()){
count++;
}
countPossibleWord(s,inputSize,start,end+1,tempCount-1);
}
}
If you like to have a recursive function, you should be clear about your parameters (use as few as possible) as well as when to step down and when to go up again. My solution would look something like
public static int countPossibleWord(String strMorse, String strAlpha, int inputSize) {
if (strMorse.length() > 0) { // still input to process
if (strAlpha.length() >= inputSize)
return 0; // String already has wrong size
int count = 0;
for (int i = 0; i < morse.length; i++) { // try all morse codes
if (strMorse.startsWith(morse[i])) { // on the beginning of the given string
count += countPossibleWord(strMorse.substring(morse[i].length()), strAlpha+alpha[i], inputSize);
}
}
return count;
} else {
if( strAlpha.length() == inputSize ) {
System.out.println( strAlpha );
return 1; // one solution has been found
} else {
return 0; // String has wrong size
}
}
}
Your morse and alpha arrays need to be static variables for this to work. Note that there is only one situation where the recursion will step down: when there is some input left and the size limit is not reached. Then it will check for the next possible letter in the loop.
All other cases will lead the recursion to go one step up again - and when going up, it will return the number of solutions found.
Call it like this:
System.out.println(countPossibleWord(morseString, "", input.length() ));