打印出所有不明确的莫尔斯鳕鱼的可能性

Question

学校给我布置了一个难题，这让我左右为难。我要做的是在一个模棱两可的莫尔斯电码串（即没有空格来说明什么是字母，什么不是），然后打印出莫尔斯电码所有可能的有效英文翻译。我在互联网上看到过一种算法来解决这个问题，但是我不知道如何将它转换成python3，我一辈子也找不到它。在

一些有用的东西：

• 我有一个程序认为有效的单词列表：Download

• 该程序不需要输出图形化正确的句子，只需要输出那些构成有效且在words.txt中的单词的句子。

• 定义一个句子是否有效的一些额外的事情是句子不能有两个相同的单词；所有单词必须是唯一的，并且句子中不能有一个1个字母的单词和一个2个字母的单词。在

• 我的电码，目前还不完整，但它把所有的单词都归类到相应的莫尔斯电码定义中：

  # Define the mapping from letter to Morse code.
  CODES = {
      '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': '--..',
  }
  words={}
  
  f=open('words.txt').read()
  a=f
  for i in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
    a=a.replace(i,CODES[i])
  f=f.split('\n')
  a=a.split('\n')
  for i in f:
        words[i]=a[f.index(i)]
      q=input('Morse: ')
  

一个关于如何工作的示例测试用例是：

^{pr2}$

Answer 1

要完成这个程序，您需要使用递归算法，因为有太多可能的单词组合。在

我已经改变了你的变量名，以便他们很容易理解他们持有什么数据。在

decode函数用作递归算法。第一行检查Morse是否为空，因此不需要运行函数，因为它是结束点，它打印该分支的输出。在

函数的其余部分将检查是否可以从第一个i字母中识别出一个单词。i从1开始，因为这是最短的字母，max length是文件中最大的Morse长度。while循环还通过检查i不大于Morse的长度来检查是否没有发生越界错误。在

代码无法更改函数的参数，因为在相同的函数中可以找到其他单词，从而导致冲突，因此为更改后的English和Morse创建了新变量。检查可能单词的长度是否重复并允许。在

from string import ascii_uppercase

#Defines the letter to Morse mapping
code = {
    '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': ' ..'
}

#Opens the file and reads all words
file = open("words.txt","r")
words = file.read()
file.close()

morse = words

# Converts all words to morse
for letter in list(ascii_uppercase):
    morse = morse.replace(letter, code[letter])

# Creates list of the morse and english words from strings
morsewords = morse.split("\n")
engwords = words.split("\n")

# Finds the max length of morse words
maxlength = max([len(i)] for i in morsewords)[0]

# Creates a dictionary of {morse words : english words}
words = dict(zip(morsewords, engwords))

# MorseInput = input("Morse code :")
MorseInput = ". ....-....-.-..  -."

# This is the recursive function
def decode(morse, eng="", oneWord=False, twoWord=False):
    # Print the english when finished
    if morse == "":
        print(eng)
    else:
        i = 1
        # While loop allows to go through all possWord where condition met
        while len(morse) >= i and i <= maxlength:
            possWord = morse[:i]
            # Checks if the word is a real word
            if possWord in words.keys():
                # Real word therefore add to english and the morse
                newEng = eng + " " + words[possWord]
                newMorse = morse[i:]
                # Checks if that not more than one, One length word used
                if len(words[possWord]) == 1:
                    if not oneWord:
                        decode(newMorse, newEng, True, twoWord)
                # Checks if that not more than one, Two length word used
                elif len(words[possWord]) == 2:
                    if not twoWord:
                        decode(newMorse, newEng, oneWord, True)
                # Word is greater than two so doesn't matter
                else:
                    decode(newMorse, newEng, oneWord, twoWord)                    
            i += 1


decode(MorseInput)

我希望我的评论能说得通。在

我确信代码可以做得更好、更短，但我在不到一个小时内就完成了。在

它印出来了

^{pr2}$