我试图解决给定一串莫尔斯电码字符在字典中找到有意义的单词的问题
例如
此输入字符串“..-.----..-.-...---..-.--”应翻译为“fox lazy”，可能有多种其他翻译，但这是一种可能的解决方案，因为这两个单词存在于英语词典中。
我写了 2 个函数，TranslateMorse 和 SegmentString。 SegmentString 分割英文字符串并查找字典中所有有意义的单词。例如，如果输入是“foxlazy”，该函数可以找到“fox”和“lazy”是字典中存在的两个有意义的单词。
TranslateMorse 实际上应该将莫尔斯电码输入“..-.----..-.-...---..-.--”翻译为“foxlazy”，以便 SegmentString 给出结果输出，但棘手的部分是莫尔斯电码翻译并不直接，它给了我很多翻译。
如何解决这个问题？
import java.util.*;
public class MorseCode {
String TranslateMorse(String input, Map<String, String> morse) {
// "-.-..-.--..--...-....---"
if (morse.containsKey(input))
return morse.get(input);
int len = input.length();
for (int i = 1; i < len; i++) {
String prefix = input.substring(0, i);
if (morse.containsKey(prefix)) {
String suffix = input.substring(i, len);
String segSuffix = SegmentString(suffix, morse);
if (segSuffix != null) {
return morse.get(prefix) + segSuffix;
}
}
}
return null;
}
String SegmentString(String input, Set<String> dict) {
if (dict.contains(input))
return input;
int len = input.length();
for (int i = 1; i < len; i++) {
String prefix = input.substring(0, i);
if (dict.contains(prefix)) {
String suffix = input.substring(i, len);
String segSuffix = SegmentString(suffix, dict);
if (segSuffix != null) {
return prefix + " " + segSuffix;
}
}
}
return null;
}
// Driver method
public static void main(String args[]) {
Map<String, String> morse = new HashMap<>();
morse.put(".-", "a");
morse.put("-...", "b");
morse.put("-.-.", "c");
morse.put("-..", "d");
morse.put(".", "e");
morse.put("..-.", "f");
morse.put("--.-", "g");
morse.put("....", "h");
morse.put("..", "i");
morse.put(".---", "j");
morse.put("-.-", "k");
morse.put(".-..", "l");
morse.put("--", "m");
morse.put("-.", "n");
morse.put("---", "o");
morse.put(".--.", "p");
morse.put("--.-", "q");
morse.put(".-.", "r");
morse.put("...", "s");
morse.put("-", "t");
morse.put("..-", "u");
morse.put("...-", "v");
morse.put(".--", "w");
morse.put("-..-", "x");
morse.put("-.--", "y");
morse.put("--..", "z");
Set<String> dict = new HashSet<>();
dict.add("apple");
dict.add("honey");
dict.add("fox");
dict.add("quick");
dict.add("jumped");
dict.add("bill");
dict.add("jam");
dict.add("holy");
dict.add("mega");
dict.add("lazy");
// fox lazy
String input = "..-.----..-.-...---..-.--";
MorseCode m = new MorseCode();
String alpha = m.TranslateMorse(input, morse);
System.out.println(alpha);
System.out.println(m.SegmentString(alpha, dict));
}
}
最佳答案
我假设这个问题的要点是莫尔斯点击流中没有字母，也没有单词，分隔符(空格)，这是分析的一部分。我发现您的代码的关键问题是:
您假设您将返回单个答案(反射(reflect)在您选择的数据类型中)，而实际上您将返回多个需要过滤的答案。
您的
TranslateMorse()方法在应该递归调用自身时调用了SegmentString()!
下面是我对代码的修改，解决了这两个问题:
import java.util.*;
public class MorseCode {
List<String> TranslateMorse(String input, Map<String, String> dictionary) {
List<String> strings = new ArrayList<String>();
if (dictionary.containsKey(input)) {
strings.add(dictionary.get(input));
}
int length = input.length();
for (int i = 1; i < length; i++) {
String prefix = input.substring(0, i);
if (dictionary.containsKey(prefix)) {
String suffix = input.substring(i, length);
List<String> translations = TranslateMorse(suffix, dictionary);
if (! translations.isEmpty()) {
String letter = dictionary.get(prefix);
for (String translation : translations) {
strings.add(letter + translation);
}
}
}
}
return strings;
}
List<String> SegmentString(String input, Set<String> wordList) {
List<String> strings = new ArrayList<String>();
if (wordList.contains(input))
strings.add(input);
int length = input.length();
for (int i = 1; i < length; i++) {
String prefix = input.substring(0, i);
if (wordList.contains(prefix)) {
String suffix = input.substring(i, length);
List<String> expansions = SegmentString(suffix, wordList);
if (! expansions.isEmpty()) {
for (String expansion : expansions) {
strings.add(prefix + " " + expansion);
}
}
}
}
return strings;
}
public static void main(String args[]) {
Map<String, String> morse = new HashMap<>();
morse.put(".-", "a");
morse.put("-...", "b");
morse.put("-.-.", "c");
morse.put("-..", "d");
morse.put(".", "e");
morse.put("..-.", "f");
morse.put("--.-", "g");
morse.put("....", "h");
morse.put("..", "i");
morse.put(".---", "j");
morse.put("-.-", "k");
morse.put(".-..", "l");
morse.put("--", "m");
morse.put("-.", "n");
morse.put("---", "o");
morse.put(".--.", "p");
morse.put("--.-", "q");
morse.put(".-.", "r");
morse.put("...", "s");
morse.put("-", "t");
morse.put("..-", "u");
morse.put("...-", "v");
morse.put(".--", "w");
morse.put("-..-", "x");
morse.put("-.--", "y");
morse.put("--..", "z");
Set<String> english = new HashSet<>();
english.add("apple");
english.add("honey");
english.add("fox");
english.add("quick");
english.add("jumped");
english.add("bill");
english.add("jam");
english.add("holy");
english.add("mega");
english.add("lazy");
String input = "..-.----..-.-...---..-.--"; // fox lazy
MorseCode decoder = new MorseCode();
List<String> decodings = decoder.TranslateMorse(input, morse);
for (String decoding : decodings) {
List<String> phrases = decoder.SegmentString(decoding, english);
for (String phrase : phrases) {
System.out.println(input + " -> " + decoding + " -> " + phrase);
}
}
}
}
使用
> java MorseCode
..-.----..-.-...---..-.-- -> foxlazy -> fox lazy
>
这不是一个快速的程序 - 在本示例中大约需要 10 秒，因为它必须将“嘀”和“哒”的所有可能解释过滤为莫尔斯电码符号，然后通过英语单词列表过滤这些解释。
关于java - 将摩尔斯电码转换为英语词典单词，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55192241/