java - 给定整数到字符的映射找到给定整数的所有可能字符组合

Question

我有一个库，其中包含从整数到字符的映射。我还有一个整数格式的字符串。我正在尝试编写一种方法，在解释字符串时将返回所有可能的字符组合。例如:给定以下库 a=1, b=2, c=3, k=11 和字符串 "1123" 输出应该是一个包含 的列表"aabc", "kbc" 假设所有给定的数字都可以在库中找到。

我目前的解决方案如下:

public static ArrayList<String> d(String s) {
    ArrayList<String> s2 = new ArrayList<String>();
    if (s.length() == 1) {
        s2.add(""+library.get(Integer.valueOf(s)));
        return s2;
    }
    for (int i=0; i < s.length(); i++) {
        String curr = s.substring(0, i + 1);
        if (library.containsKey(Integer.valueOf(curr))){
            ArrayList<String> strings = d(s.substring(i + 1));
            char c2 = library.get(Integer.valueOf(curr));
            for (String tmp : strings){
                s2.add(c2 + tmp);
            }
        }
    }
    return s2;
}

有没有更优化的方法来解决这个问题？另外，我的解决方案的复杂性是什么？我的假设是 O(N^3) 时间。

Answer 1

您的问题映射到以下语法:

S -> SA | SB | SC | SK | ε
A -> 1
B -> 2
C -> 3
K -> 11

这是一个上下文无关的语法，这意味着任何体面的解析器( CYK ， Earley )将在 O(n³) 时间内解析它作为最坏的情况。任何比这更糟糕的事情，你肯定走错了路。

(注意:虽然语法是上下文无关的，但它定义的语言实际上是规则的。增加的复杂性来自于我们生成所有可能的解析树的要求。如果要求只是判断一个整数是否是一个整数我们语言中的有效句子，正则表达式 ((1)|(2)|(3)|(11))+ 就足够了)