问题陈述:
给定一个数字序列,计算可能的解码方式。
例子:
12 的解码方式有2种: 'AB' 和 'L'
123 的解码方式有3种: 'ABC', 'LC' 和 'AW'
这是我的尝试:
例子:
12 的解码方式有2种: 'AB' 和 'L'
123 的解码方式有3种: 'ABC', 'LC' 和 'AW'
这是我的尝试:
import java.util.*;
public class decodingcount {
static int calls = 0;
static Map<Integer, String> codes = new HashMap<Integer, String>();
private static void construct(){
codes.put(1, "A");
codes.put(2, "B");
codes.put(3, "C");
codes.put(4, "D");
//..so on
}
private static int decode(String str, String built){
construct();
int n = str.length();
int count = 0;
if (n == 0) {
System.out.println(built);
return 1;
}
// If you have 0's, then they don't have a corresponding singular letter. Break off the recursion.
if (str.substring(0, 1).equals("0"))
return 0;
String x = codes.get(Integer.parseInt(str.substring(0, 1)));
if (x == null)
return 0;
count = decode(str.substring(1), built+x);
if (n > 1) {
// If it's more than 26, it doesn't have a corresponding letter. Break off the recursion.
if (Integer.parseInt(str.substring(0, 2)) > 26)
return 0;
String y = codes.get(Integer.parseInt(str.substring(0, 2)));
count += decode(str.substring(2), built+y);
}
return count;
}
public static void main(String[] args) {
System.out.println(decode(args[0], ""));
}
}
这个算法运行时间是指数级别的。我很难将其转换为一种动态规划的自底向上的表格化算法。这是我的尝试,但它返回了0。如果能得到任何帮助,将不胜感激。