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

Question

我必须在给定的摩尔斯电码中找到所有可能的字母组合。解码单词的长度可以是最多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

我应该改变什么才能获得所有这些？谢谢你的时间和回答！

Answer 1

c++解决方案：

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

char buffer[26];
int l=0;
char *Morse[26];
//initializing Morse Code array
void initMorse(){
Morse[0] = "._" ;            
Morse[1] = "_...";            
Morse[2] = "_._." ;            
Morse[3] = "_.." ;            
Morse[4] = "." ;   //E         
Morse[5] = ".._." ;            
Morse[6] = "__." ;            
Morse[7] = "...." ;  //H          
Morse[8] = ".." ;       //I     
Morse[9] = ".___" ;   //J         
Morse[10] = "_._" ;  //K            
Morse[11] = "._.." ;            
Morse[12] = "__" ;   //M         
Morse[13] = "_." ;            
Morse[14] = "___" ;     //O       
Morse[15] = ".__." ;  //P            
Morse[16] = "__._" ;            
Morse[17] = "._." ;   //R         
Morse[18] = "..." ;            
Morse[19] = "_" ;            
Morse[20] = ".._" ;            
Morse[21] = "..._" ;  //V          
Morse[22] = ".__" ;            
Morse[23] = "_.._" ;            
Morse[24] = "_.__" ;            
Morse[25] = "__.." ; //Z
}
int solution(char *s,int strt,char **Morse,int len){
    int i,j,noMatch=0,k,prev,tem;
    int mlen;
    if(strt!=len)
    for(i=0;i<26;i++){
    mlen=strlen(Morse[i]);
     if(strt+mlen<=len){
        for(j=strt,k=0;j<strt+mlen&&k<mlen;j++,k++){
            if(Morse[i][k]==s[j])
                continue;
            else {
                noMatch=1;
                break;
            }
        }
    }
    else{
        continue;   
    }
    if(noMatch==0){
         //print pattern when complete string matched
         if(strt+mlen==len){
          buffer[l]=i+65;
             printf("%s\n",buffer);
             buffer[l]=0;
        }
        else{
            noMatch=0;  
            buffer[l]=i+65;
            l++;
            solution(s,strt+mlen,Morse,len);
            l--;                 // while backtracking 
            buffer[l]=0;      //  clearing buffer just upto the previous location 
        }
    }
    else{
        noMatch=0;
    }
}
else{
    buffer[l]=0;
}
return 1;
}

int main() {

char s[100];
printf("Enter the input string of Morse code:\n");
scanf("%s",s);
initMorse();
printf("Possible translations are:\n");
solution(s,0,Morse,strlen(s));
for
return 0;
}

Answer 2

我建议使用递归和字典将莫尔斯电码映射到字母（而不是字母到莫尔斯电码）：

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("\n") 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

Answer 3

这是一个可行的解决方案。我对评论和答案中的代码和建议进行了更改。（翻译的莫尔斯电码也不一样）

    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:
                new_start = start + len(my_dict[char])
                new_word = word + char
                adding_to_set(given_morse, my_set, my_dict, new_word, new_start)
                if word_to_morse(new_word, my_dict) == given_morse:
                    my_set.add(new_word)
    words = set()

    # the morse code I want to decrypt
    morse = '.-.--...-....-.'

    # adding morse alphabet here
    pairs={'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': '--..',

     
    }
    adding_to_set(morse, words, pairs)
    print(len(words))
    print(words)

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

Python, find all the possible letter combinations in given morse code

python

decode

morse-code