Python，找出给定摩尔斯电码中所有可能的字母组合

问题描述

我必须在给定的莫尔斯电码中找到所有可能的字母组合。解码单词的长度最多为10个字母。包含字母和摩尔斯电码的给定文件如下所示：

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   --..

给定的摩尔斯电码如下：

morse = '-.----.-.-...----.-.-.-.----.-'

我的代码如下：

def morse_file_to_dict(filename):
    with open(filename) as file:
        return dict(line.strip().split() for line in file)


def word_to_morse(s, my_dict):
    return ''.join([my_dict[w] for w in s])


def adding_to_set(given_morse, my_set, my_dict, word='', start=0):
    for char in my_dict:
        if my_dict[char] == given_morse[start:start + len(my_dict[char])] and len(word) < 10:
            start = start + len(my_dict[char])
            word = word + char
            adding_to_set(given_morse, my_set, my_dict, word, start)
            if word_to_morse(word, my_dict) == given_morse:
                my_set.add(word)


words = set()
morse = '-.----.-.-...----.-.-.-.----.-'
pairs = morse_file_to_dict('morse_alphabet.txt')
adding_to_set(morse, words, pairs)
print(len(words))
print(words)

我的输出是：

5
{'KMCBMQRKMK', 'KMCBMGKRMQ', 'KMCBMGCKMK', 'KMNCEJCCMQ', 'KMCDAMCCMQ'}

但是，答案应该是：10571字，而不是5个

我应该更改什么才能获得所有这些内容？ 感谢您的宝贵时间和答复！

---

解决方案

我建议使用递归和词典将摩尔斯代码映射到字母(而不是字母到莫尔斯代码)：

morseFile="""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   --.."""

morse = {code:letter for line in morseFile.split("
") for letter,code in [line.split()]}

可以将该函数构建为生成器，以避免将所有可能性存储在一个大列表中：

def decode(coded,maxLen=10):
    if not maxLen: return
    for size in range(1,min(4,len(coded))+1):
        code = coded[:size]
        if code not in morse: continue
        remaining = coded[size:]
        if not remaining: yield morse[code]
        for rest in decode(remaining,maxLen-1):
            yield morse[code] + rest

输出：

print(sum(1 for _ in decode("-.----.-.-...----.-.-.-.----.-")))

10571

for string in decode("-.----.-.-...----.-.-.-.----.-"):
    if len(string)<9: print(string)

YQLWGCYQ
YQLWQRYQ
YQLJNCYQ
YQLJKRYQ
YQLJCNYQ
YQLJCKWQ
YQLJCKJK
YQLJCCMQ
YQLJCCOK