Morse code intepretor


  • 1
    Y

    You are given a sequence of morse code with no break in between. you will have to return all the possibility of English interpretation from the given morse code sequence.


  • 0
    S

    We can solve the problem of finding all possible sentences given a list of characters. We can translate the original problem into this one by simply translating morse code into characters using a dictionary mapping morse code sequences to chars.

    Then we can solve the problem using recursion:

    // a sentence is a List<String>, where each String is a word from dictionary
    public static List<List<String>> findSentences(char[] chars) {
        int n = chars.length;
        List<List<String>> sentences = new ArrayList<>();
        StringBuilder word = new StringBuilder();
        for (int i = 0; i < n; i++) {
            word.append(chars[i]);
            if (dictionary.contains(word.toString())) {
                if (n - i > 1) {
                    char[] rest = new char[n - i - 1];
                    System.arraycopy(chars, i + 1, rest, 0, n - i - 1);
                    List<List<String>> sentencesStartingWithWord = findSentences(rest);
                    if (sentencesStartingWithWord != null) {
                        for (List<String> sentence : sentencesStartingWithWord)
                            sentence.add(0, word.toString());
                        sentences.addAll(sentencesStartingWithWord);
                    }
                }
            }
        }
        if (dictionary.contains(word.toString())) {
            // all chars form a single word
            List<String> sentenceWithOneWord = new ArrayList<>();
            sentenceWithOneWord.add(word.toString());
            sentences.add(sentenceWithOneWord);
        }
        if (sentences.isEmpty()) {
            // haven't found any sentence using chars, so return null
            sentences = null;
        }
        return sentences;
    }
    

    We can improve recursion using memoization.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.