给定一个没有任何空格的莫尔斯弦，如何找到号码。它可以代表的词的数量，无论其含义如何
Given a Morse String with out any spaces, how to find the no. of words it can represent irrespective of the meaning
给定一个莫尔斯字符串，例如。 aet = ".- .-" 如果去掉空格就会变成一个模棱两可的莫尔斯串 ".-.-" 可以表示 "aet","eta","ent","etet"等
题目是找出no.of个不带空格的摩尔斯串可以表示的单词，不管单词的意思。约束是形成的新词应该与输入的大小相同，即 "aet" = "ent" 和其他像 "etet" 的词应该被丢弃。
我实施了一个递归解决方案，但由于某种原因它不起作用。下面是我的代码，并考虑将其转换为 DP 方法以提高时间效率。有人可以帮助指出以下代码中的错误吗？DP 是解决此问题的正确方法吗？提前致谢！！
编辑 1 :- 该程序给了我一个输出但不是正确的输出。例如。对于表示 aet = ".- .-" 的莫尔斯字符串，如果在程序 ".-.-" 中没有任何空格，它应该给出输出 "3"，即可以形成 3 个与输入包括输入 "aet"、"eta"、"ent" 但它给了我一个输出“1”。我认为递归调用有些问题。
这里使用的方法是简单地在遇到第一个有效莫尔斯电码的地方剪切莫尔斯字符串，然后对字符串的其余部分重复该过程，直到找到 3 个这样的有效莫尔斯电码，并检查是否是整个莫尔斯电码字符串被消耗。如果消耗增加字数并针对子字符串大小的不同值重复该过程（下面代码中的结束变量）。
希望对您有所帮助！！已尽力解释清楚。
import java.util.*;
import java.io.*;
import java.math.*;
import java.text.*;
public class MorseCode2 {
static Map<String,String> morseCode;
static Map<String,String> morseCode2;
static int count = 0;
public static void main(String args[]){
String[] alpha = {"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"};
String[] morse = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",
".--","-..-","-.--","--.."};
morseCode = new HashMap<String,String>();
morseCode2 = new HashMap<String,String>();
for(int i = 0;i<26;i++){
morseCode.put(morse[i],alpha[i]);
}
for(int i = 0;i<26;i++){
morseCode2.put(alpha[i],morse[i]);
}
Scanner in = new Scanner(System.in);
String input = in.next();
String morseString = "";
for(int j = 0; j< input.length(); j++){
morseString += morseCode2.get(input.charAt(j)+"");
}
countPossibleWord(morseString,input.length(),0,1,0);
System.out.println(count);
in.close();
}
public static void countPossibleWord(String s,int inputSize,int start,int end,int tempCount){
if(start >= s.length() || end > s.length()){
return;
}
if(tempCount>inputSize){
return;
}
String sub = s.substring(start, end);
if(sub.length()>4){
return;
}
if(morseCode.get(sub)!=null){
tempCount++;
countPossibleWord(s,inputSize,end,end+1,tempCount);
}
else{
countPossibleWord(s,inputSize,start,end+1,tempCount);
}
if(tempCount == inputSize && end == s.length()){
count++;
}
countPossibleWord(s,inputSize,start,end+1,0);
}
}
编辑 2 :- 感谢大家的回复，对于混乱的代码深表歉意，一定会努力改进编写整洁清晰的代码。从你的回复中学到了很多！！
我还了解了代码是如何工作的，问题是我传递了错误的参数，这改变了递归调用的状态。在方法 "countPossibleWord" 的最后一个函数调用中，我没有为最后一个参数传递 "tempCount-1"，而是传递了“0”，这改变了状态。在 运行 之后通过代码手动找到这个以获得更大的输入。下面是修正后的方法
public static void countPossibleWord(String s,int inputSize,int start,int end,int tempCount){
if(start >= s.length() || end > s.length()){
return;
}
if(tempCount>inputSize){
return;
}
String sub = s.substring(start, end);
if(sub.length()>4){
return;
}
if(morseCode.get(sub)!=null){
tempCount++;
countPossibleWord(s,inputSize,end,end+1,tempCount);
}
else{
countPossibleWord(s,inputSize,start,end+1,tempCount);
}
if(tempCount == inputSize && end == s.length()){
count++;
}
countPossibleWord(s,inputSize,start,end+1,tempCount-1);
}
}
您的代码的问题是，您不再理解它，因为它不像 Robert C. Martin 所描述的那样干净。将您的代码与以下代码进行比较。这当然不是最干净的，但我想你可以理解它的作用。如果你不知道，请告诉我。
考虑这个主程序：
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Program {
public static void main(String[] args) {
String morsetext = enterTextOnConsole();
MorseTable morseTable = new MorseTable();
MorseCode code = convertToMorseCodeWithoutSpaces(morsetext, morseTable);
List<String> guesses = getAllPossibleMeanings(code, morseTable);
List<String> guessesOfSameLength = filterForSameLength(morsetext, guesses);
printListOnConsole(guessesOfSameLength);
}
private static void printListOnConsole(List<String> guessesOfSameLength) {
for (String text : guessesOfSameLength) {
System.out.println(text);
}
}
private static List<String> filterForSameLength(String morsetext, List<String> guesses) {
List<String> guessesOfSameLength = new LinkedList<String>();
for (String guess : guesses) {
if (guess.length() == morsetext.length())
{
guessesOfSameLength.add(guess);
}
}
return guessesOfSameLength;
}
private static List<String> getAllPossibleMeanings(MorseCode code, MorseTable morseTable) {
MorseCodeGuesser guesser = new MorseCodeGuesser(morseTable);
List<String> guesses = guesser.guess(code);
return guesses;
}
private static MorseCode convertToMorseCodeWithoutSpaces(String morsetext, MorseTable morseTable) {
MorseCode code = new MorseCode(morseTable);
code.fromText(morsetext);
code.stripSpaces();
return code;
}
private static String enterTextOnConsole() {
Scanner scanner = new Scanner(System.in);
String text = scanner.next();
scanner.close();
return text;
}
}
和以下 MorseTable class：
import java.util.HashMap;
import java.util.Map;
public class MorseTable {
private static final Map<String, String> morseTable;
private static int longestCode = -1;
static
{
morseTable = new HashMap<String, String>();
morseTable.put("a", ".-");
morseTable.put("b", "-...");
morseTable.put("c", "-.-.");
morseTable.put("e", ".");
morseTable.put("t", "-");
morseTable.put("n", "-.");
// TODO: add more codes
for (String code : morseTable.values()) {
longestCode = Math.max(longestCode, code.length());
}
}
public String getMorseCodeForCharacter(char c) throws IllegalArgumentException {
String characterString = ""+c;
if (morseTable.containsKey(characterString)) {
return morseTable.get(characterString);
}
else {
throw new IllegalArgumentException("No morse code for '"+characterString+"'.");
}
}
public int lengthOfLongestMorseCode() {
return longestCode;
}
public String getTextForMorseCode(String morseCode) throws IllegalArgumentException {
for (String key : morseTable.keySet()) {
if (morseTable.get(key).equals(morseCode)) {
return key;
}
}
throw new IllegalArgumentException("No character for morse code '"+morseCode+"'.");
}
}
和摩尔斯电码class
public class MorseCode {
public MorseCode(MorseTable morseTable)
{
_morseTable = morseTable;
}
final MorseTable _morseTable;
String morseCode = "";
public void fromText(String morsetext) {
for(int i=0; i<morsetext.length(); i++) {
char morseCharacter = morsetext.charAt(i);
morseCode += _morseTable.getMorseCodeForCharacter((morseCharacter));
morseCode += " "; // pause between characters
}
}
public void stripSpaces() {
morseCode = morseCode.replaceAll(" ", "");
}
public MorseCode substring(int begin, int end) {
MorseCode subcode = new MorseCode(_morseTable);
try{
subcode.morseCode = morseCode.substring(begin, end);
} catch(StringIndexOutOfBoundsException s) {
subcode.morseCode = "";
}
return subcode;
}
public MorseCode substring(int begin) {
return substring(begin, morseCode.length());
}
public String asPrintableString() {
return morseCode;
}
public boolean isEmpty() {
return morseCode.isEmpty();
}
}
最后一点，MorseCodeGuesser
import java.util.LinkedList;
import java.util.List;
public class MorseCodeGuesser {
private final MorseTable _morseTable;
public MorseCodeGuesser(MorseTable morseTable) {
_morseTable = morseTable;
}
public List<String> guess(MorseCode code) {
List<String> wordList = new LinkedList<String>();
if (code.isEmpty()) return wordList;
for(int firstCodeLength=1; firstCodeLength<=_morseTable.lengthOfLongestMorseCode(); firstCodeLength++) {
List<String> guesses = guess(code, firstCodeLength);
wordList.addAll(guesses);
}
return wordList;
}
private List<String> guess(MorseCode code, int firstCodeLength) {
MorseCode firstCode = code.substring(0, firstCodeLength);
String firstCharacter;
try{
firstCharacter = _morseTable.getTextForMorseCode(firstCode.asPrintableString());
} catch(IllegalArgumentException i) {
return new LinkedList<String>(); // no results for invalid code
}
MorseCode remainingCode = code.substring(firstCodeLength);
if (remainingCode.isEmpty()) {
List<String> result = new LinkedList<String>();
result.add(firstCharacter); // sole result if nothing is left
return result;
}
List<String> result = new LinkedList<String>();
List<String> remainingPossibilities = guess(remainingCode);
for (String possibility : remainingPossibilities) {
result.add(firstCharacter + possibility); // combined results
}
return result;
}
}
您使用 class 变量而不是递归函数的返回值这一事实使其非常不清楚。甚至正如@Thomas Weller 所说的那样。当你再数一个字母时，你应该澄清可能的情况。我删除了 eclipse，因此我用 C 编写了它，我希望我仍然能帮助你理解算法:(将 char* 理解为字符串)
char morse[26][5] = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",
".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
int countPossibleWord(char* s, int inputSize, int start, char* buffer, int sizeBuff){
if(start == inputSize){
if(sizeBuff == 0) return 1;
else return 0;
}
char buff[sizeBuff+2]; //
strncpy(buff, buffer, sizeBuff);//
buff[sizeBuff] = s[start]; // buff = buff+s[start]
buff[sizeBuff+1] = '[=10=]'; //
for(int i = 0; i < 26; ++i){
//run the equivalent of your map to find a match
if(strcmp(buff, morse[i]) == 0)
return countPossibleWord(s, inputSize, start+1, "", 0) + countPossibleWord(s, inputSize, start+1, buff, sizeBuff+1);
}
return countPossibleWord(s, inputSize, start+1, buff, sizeBuff+1);
}
如果你喜欢递归函数，你应该清楚你的参数（尽可能少用）以及什么时候下台，什么时候再上去。
我的解决方案看起来像
public static int countPossibleWord(String strMorse, String strAlpha, int inputSize) {
if (strMorse.length() > 0) { // still input to process
if (strAlpha.length() >= inputSize)
return 0; // String already has wrong size
int count = 0;
for (int i = 0; i < morse.length; i++) { // try all morse codes
if (strMorse.startsWith(morse[i])) { // on the beginning of the given string
count += countPossibleWord(strMorse.substring(morse[i].length()), strAlpha+alpha[i], inputSize);
}
}
return count;
} else {
if( strAlpha.length() == inputSize ) {
System.out.println( strAlpha );
return 1; // one solution has been found
} else {
return 0; // String has wrong size
}
}
}
你的莫尔斯和阿尔法数组需要是静态变量才能工作。
请注意，只有一种情况下递归会下降：当还剩下一些输入且未达到大小限制时。然后它将检查循环中的下一个可能的字母。
所有其他情况将导致递归再次上升一级 - 上升时，它将 return 找到的解决方案数量。
这样称呼它：
System.out.println(countPossibleWord(morseString, "", input.length() ));
我贴了自己的解决方法。我关注了 DFS，它给出了给定问题陈述的正确答案。有问题请追问
alpha =["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"]
key = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--",
"-..-","-.--","--.."]
dic = dict(list(zip(key,alpha)))
def morse_code(morse,count,res,char,length):
global dic
if count == length - 1:
if morse[char:] in dic:
res = res + 1
return res
word = ''
for i in range(char,len(morse)):
word = word + morse[i]
if word not in dic:
continue
else:
count = count + 1
res = morse_code(morse,count,res,i+1,length)
count = count - 1
return res
if __name__ = 'main'
inp = input()
morse = ''
for i in inp:
morse = morse + key[ord(i)-ord('a')]
result = morse_code(morse,0,0,0,len(inp))
print(result)
给定一个莫尔斯字符串，例如。 aet = ".- .-" 如果去掉空格就会变成一个模棱两可的莫尔斯串 ".-.-" 可以表示 "aet","eta","ent","etet"等
题目是找出no.of个不带空格的摩尔斯串可以表示的单词，不管单词的意思。约束是形成的新词应该与输入的大小相同，即 "aet" = "ent" 和其他像 "etet" 的词应该被丢弃。
我实施了一个递归解决方案，但由于某种原因它不起作用。下面是我的代码，并考虑将其转换为 DP 方法以提高时间效率。有人可以帮助指出以下代码中的错误吗？DP 是解决此问题的正确方法吗？提前致谢！！
编辑 1 :- 该程序给了我一个输出但不是正确的输出。例如。对于表示 aet = ".- .-" 的莫尔斯字符串，如果在程序 ".-.-" 中没有任何空格，它应该给出输出 "3"，即可以形成 3 个与输入包括输入 "aet"、"eta"、"ent" 但它给了我一个输出“1”。我认为递归调用有些问题。
这里使用的方法是简单地在遇到第一个有效莫尔斯电码的地方剪切莫尔斯字符串，然后对字符串的其余部分重复该过程，直到找到 3 个这样的有效莫尔斯电码，并检查是否是整个莫尔斯电码字符串被消耗。如果消耗增加字数并针对子字符串大小的不同值重复该过程（下面代码中的结束变量）。
希望对您有所帮助！！已尽力解释清楚。
import java.util.*;
import java.io.*;
import java.math.*;
import java.text.*;
public class MorseCode2 {
static Map<String,String> morseCode;
static Map<String,String> morseCode2;
static int count = 0;
public static void main(String args[]){
String[] alpha = {"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"};
String[] morse = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",
".--","-..-","-.--","--.."};
morseCode = new HashMap<String,String>();
morseCode2 = new HashMap<String,String>();
for(int i = 0;i<26;i++){
morseCode.put(morse[i],alpha[i]);
}
for(int i = 0;i<26;i++){
morseCode2.put(alpha[i],morse[i]);
}
Scanner in = new Scanner(System.in);
String input = in.next();
String morseString = "";
for(int j = 0; j< input.length(); j++){
morseString += morseCode2.get(input.charAt(j)+"");
}
countPossibleWord(morseString,input.length(),0,1,0);
System.out.println(count);
in.close();
}
public static void countPossibleWord(String s,int inputSize,int start,int end,int tempCount){
if(start >= s.length() || end > s.length()){
return;
}
if(tempCount>inputSize){
return;
}
String sub = s.substring(start, end);
if(sub.length()>4){
return;
}
if(morseCode.get(sub)!=null){
tempCount++;
countPossibleWord(s,inputSize,end,end+1,tempCount);
}
else{
countPossibleWord(s,inputSize,start,end+1,tempCount);
}
if(tempCount == inputSize && end == s.length()){
count++;
}
countPossibleWord(s,inputSize,start,end+1,0);
}
}
编辑 2 :- 感谢大家的回复，对于混乱的代码深表歉意，一定会努力改进编写整洁清晰的代码。从你的回复中学到了很多！！
我还了解了代码是如何工作的，问题是我传递了错误的参数，这改变了递归调用的状态。在方法 "countPossibleWord" 的最后一个函数调用中，我没有为最后一个参数传递 "tempCount-1"，而是传递了“0”，这改变了状态。在 运行 之后通过代码手动找到这个以获得更大的输入。下面是修正后的方法
public static void countPossibleWord(String s,int inputSize,int start,int end,int tempCount){
if(start >= s.length() || end > s.length()){
return;
}
if(tempCount>inputSize){
return;
}
String sub = s.substring(start, end);
if(sub.length()>4){
return;
}
if(morseCode.get(sub)!=null){
tempCount++;
countPossibleWord(s,inputSize,end,end+1,tempCount);
}
else{
countPossibleWord(s,inputSize,start,end+1,tempCount);
}
if(tempCount == inputSize && end == s.length()){
count++;
}
countPossibleWord(s,inputSize,start,end+1,tempCount-1);
}
}
您的代码的问题是，您不再理解它，因为它不像 Robert C. Martin 所描述的那样干净。将您的代码与以下代码进行比较。这当然不是最干净的，但我想你可以理解它的作用。如果你不知道，请告诉我。
考虑这个主程序：
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Program {
public static void main(String[] args) {
String morsetext = enterTextOnConsole();
MorseTable morseTable = new MorseTable();
MorseCode code = convertToMorseCodeWithoutSpaces(morsetext, morseTable);
List<String> guesses = getAllPossibleMeanings(code, morseTable);
List<String> guessesOfSameLength = filterForSameLength(morsetext, guesses);
printListOnConsole(guessesOfSameLength);
}
private static void printListOnConsole(List<String> guessesOfSameLength) {
for (String text : guessesOfSameLength) {
System.out.println(text);
}
}
private static List<String> filterForSameLength(String morsetext, List<String> guesses) {
List<String> guessesOfSameLength = new LinkedList<String>();
for (String guess : guesses) {
if (guess.length() == morsetext.length())
{
guessesOfSameLength.add(guess);
}
}
return guessesOfSameLength;
}
private static List<String> getAllPossibleMeanings(MorseCode code, MorseTable morseTable) {
MorseCodeGuesser guesser = new MorseCodeGuesser(morseTable);
List<String> guesses = guesser.guess(code);
return guesses;
}
private static MorseCode convertToMorseCodeWithoutSpaces(String morsetext, MorseTable morseTable) {
MorseCode code = new MorseCode(morseTable);
code.fromText(morsetext);
code.stripSpaces();
return code;
}
private static String enterTextOnConsole() {
Scanner scanner = new Scanner(System.in);
String text = scanner.next();
scanner.close();
return text;
}
}
和以下 MorseTable class：
import java.util.HashMap;
import java.util.Map;
public class MorseTable {
private static final Map<String, String> morseTable;
private static int longestCode = -1;
static
{
morseTable = new HashMap<String, String>();
morseTable.put("a", ".-");
morseTable.put("b", "-...");
morseTable.put("c", "-.-.");
morseTable.put("e", ".");
morseTable.put("t", "-");
morseTable.put("n", "-.");
// TODO: add more codes
for (String code : morseTable.values()) {
longestCode = Math.max(longestCode, code.length());
}
}
public String getMorseCodeForCharacter(char c) throws IllegalArgumentException {
String characterString = ""+c;
if (morseTable.containsKey(characterString)) {
return morseTable.get(characterString);
}
else {
throw new IllegalArgumentException("No morse code for '"+characterString+"'.");
}
}
public int lengthOfLongestMorseCode() {
return longestCode;
}
public String getTextForMorseCode(String morseCode) throws IllegalArgumentException {
for (String key : morseTable.keySet()) {
if (morseTable.get(key).equals(morseCode)) {
return key;
}
}
throw new IllegalArgumentException("No character for morse code '"+morseCode+"'.");
}
}
和摩尔斯电码class
public class MorseCode {
public MorseCode(MorseTable morseTable)
{
_morseTable = morseTable;
}
final MorseTable _morseTable;
String morseCode = "";
public void fromText(String morsetext) {
for(int i=0; i<morsetext.length(); i++) {
char morseCharacter = morsetext.charAt(i);
morseCode += _morseTable.getMorseCodeForCharacter((morseCharacter));
morseCode += " "; // pause between characters
}
}
public void stripSpaces() {
morseCode = morseCode.replaceAll(" ", "");
}
public MorseCode substring(int begin, int end) {
MorseCode subcode = new MorseCode(_morseTable);
try{
subcode.morseCode = morseCode.substring(begin, end);
} catch(StringIndexOutOfBoundsException s) {
subcode.morseCode = "";
}
return subcode;
}
public MorseCode substring(int begin) {
return substring(begin, morseCode.length());
}
public String asPrintableString() {
return morseCode;
}
public boolean isEmpty() {
return morseCode.isEmpty();
}
}
最后一点，MorseCodeGuesser
import java.util.LinkedList;
import java.util.List;
public class MorseCodeGuesser {
private final MorseTable _morseTable;
public MorseCodeGuesser(MorseTable morseTable) {
_morseTable = morseTable;
}
public List<String> guess(MorseCode code) {
List<String> wordList = new LinkedList<String>();
if (code.isEmpty()) return wordList;
for(int firstCodeLength=1; firstCodeLength<=_morseTable.lengthOfLongestMorseCode(); firstCodeLength++) {
List<String> guesses = guess(code, firstCodeLength);
wordList.addAll(guesses);
}
return wordList;
}
private List<String> guess(MorseCode code, int firstCodeLength) {
MorseCode firstCode = code.substring(0, firstCodeLength);
String firstCharacter;
try{
firstCharacter = _morseTable.getTextForMorseCode(firstCode.asPrintableString());
} catch(IllegalArgumentException i) {
return new LinkedList<String>(); // no results for invalid code
}
MorseCode remainingCode = code.substring(firstCodeLength);
if (remainingCode.isEmpty()) {
List<String> result = new LinkedList<String>();
result.add(firstCharacter); // sole result if nothing is left
return result;
}
List<String> result = new LinkedList<String>();
List<String> remainingPossibilities = guess(remainingCode);
for (String possibility : remainingPossibilities) {
result.add(firstCharacter + possibility); // combined results
}
return result;
}
}
您使用 class 变量而不是递归函数的返回值这一事实使其非常不清楚。甚至正如@Thomas Weller 所说的那样。当你再数一个字母时，你应该澄清可能的情况。我删除了 eclipse，因此我用 C 编写了它，我希望我仍然能帮助你理解算法:(将 char* 理解为字符串)
char morse[26][5] = {".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",
".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
int countPossibleWord(char* s, int inputSize, int start, char* buffer, int sizeBuff){
if(start == inputSize){
if(sizeBuff == 0) return 1;
else return 0;
}
char buff[sizeBuff+2]; //
strncpy(buff, buffer, sizeBuff);//
buff[sizeBuff] = s[start]; // buff = buff+s[start]
buff[sizeBuff+1] = '[=10=]'; //
for(int i = 0; i < 26; ++i){
//run the equivalent of your map to find a match
if(strcmp(buff, morse[i]) == 0)
return countPossibleWord(s, inputSize, start+1, "", 0) + countPossibleWord(s, inputSize, start+1, buff, sizeBuff+1);
}
return countPossibleWord(s, inputSize, start+1, buff, sizeBuff+1);
}
如果你喜欢递归函数，你应该清楚你的参数（尽可能少用）以及什么时候下台，什么时候再上去。 我的解决方案看起来像
public static int countPossibleWord(String strMorse, String strAlpha, int inputSize) {
if (strMorse.length() > 0) { // still input to process
if (strAlpha.length() >= inputSize)
return 0; // String already has wrong size
int count = 0;
for (int i = 0; i < morse.length; i++) { // try all morse codes
if (strMorse.startsWith(morse[i])) { // on the beginning of the given string
count += countPossibleWord(strMorse.substring(morse[i].length()), strAlpha+alpha[i], inputSize);
}
}
return count;
} else {
if( strAlpha.length() == inputSize ) {
System.out.println( strAlpha );
return 1; // one solution has been found
} else {
return 0; // String has wrong size
}
}
}
你的莫尔斯和阿尔法数组需要是静态变量才能工作。 请注意，只有一种情况下递归会下降：当还剩下一些输入且未达到大小限制时。然后它将检查循环中的下一个可能的字母。
所有其他情况将导致递归再次上升一级 - 上升时，它将 return 找到的解决方案数量。
这样称呼它：
System.out.println(countPossibleWord(morseString, "", input.length() ));
我贴了自己的解决方法。我关注了 DFS，它给出了给定问题陈述的正确答案。有问题请追问
alpha =["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"]
key = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--",
"-..-","-.--","--.."]
dic = dict(list(zip(key,alpha)))
def morse_code(morse,count,res,char,length):
global dic
if count == length - 1:
if morse[char:] in dic:
res = res + 1
return res
word = ''
for i in range(char,len(morse)):
word = word + morse[i]
if word not in dic:
continue
else:
count = count + 1
res = morse_code(morse,count,res,i+1,length)
count = count - 1
return res
if __name__ = 'main'
inp = input()
morse = ''
for i in inp:
morse = morse + key[ord(i)-ord('a')]
result = morse_code(morse,0,0,0,len(inp))
print(result)