给定整数到字符的映射，找出给定整数的所有可能字符组合。

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)时间。

- RagHaven

---

考虑到输出大小可能与输入长度呈指数关系，因此它绝对不是O(N^3)。 - user2357112

你应该指定一些限制。你没有指定任何限制。这个库中的整数有多大，输入字符串有多长等等？ - peter.petrov

我在Glassdoor上找到了这个问题，没有提供任何限制。http://www.glassdoor.com/Interview/Given-a-library-of-numbers-to-corresponding-letters-1-a-2-b-3-c-etc-and-a-string-made-up-of-digits-return-how-QTN_613215.htm - RagHaven

那个问题只需要你返回可能翻译的数量，而不是所有翻译的列表。这使得事情变得更容易。 - user2357112

如果只是数字，事情会变得简单一些。但是OP提出的问题是关于返回列表的。 - biziclop

Answer 1

你的问题对应以下语法：

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

这是一个无上下文文法，这意味着任何像CYK、Earley这样的好的解析器都可以在O(n³)的时间内解析它，即使最坏情况下也是如此。如果超过这个复杂度，那么你肯定走错了方向。

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

- biziclop

---

任何一个像样的解析器，如果只需要返回一棵解析树，它都可以在O(n^3)的时间内解析。但是如果要返回所有可能的解析树，则可能需要花费更长的时间。 - user2357112

Answer 2

这个问题让我想起了谷歌面试中曾经问过的一个问题：

编写一个程序，计算构建高度为N的乐高塔的所有不同方式，其中乐高块的长度和宽度均为1，高度由集合给出（例如[1,2,3,4]）。

在我们的情况下，`library`是集合，我们必须考虑一个额外的约束条件：一块乐高必须与文本匹配。

基于此，我们可以尝试使用动态规划解决方案来计算可能的“构建”数量：

public static int nCases(String s)
{
    int ncases[] = new int[s.length()];
    for(int i = 0; i < s.length(); i++)
    {
        ncases[i] = 0;
        for(Map.Entry<Integer,Character> piece: library.entrySet())
        {
            String mapStr = piece.getKey().toString();
            int j = i+1-mapStr.length();
            int prev = 1;
            if(j-1>=0) prev = ncases[j-1];
            if(j>= 0 && s.substring(j, i+1).equals(mapStr))
                ncases[i] += prev;
        }
    }
    if(ncases.length>0)
        return ncases[ncases.length-1];
    return 0;
}

这个解决方案可以轻松修改以跟踪每个案例并提供您所需的列表：

private static class Pair<T,L>
{

    public Pair(T first, L second) {
        this.first = first;
        this.second = second;
    }

    T first;
    L second;
}

public static  List<String> dynamicd(String s)
{
    Pair<Integer,List<String>> ncases[] = new Pair[s.length()];
    for(int i = 0; i < s.length(); i++)
    {
        ncases[i] = new Pair<Integer, List<String>>(0, new ArrayList<String>());
        for(Map.Entry<Integer,Character> piece: library.entrySet())
        {
            String mapStr = piece.getKey().toString();
            int j = i+1-mapStr.length();
            Pair<Integer, List<String>> prev = 
                new Pair<Integer, List<String>>(1,new ArrayList<String>());
            prev.second.add("");
            if(j-1>=0) prev = ncases[j-1];
            if(j>= 0 && s.substring(j, i+1).equals(mapStr))
            {
                ncases[i].first += prev.first;
                for(String pcase: prev.second)
                    ncases[i].second.add(pcase+piece.getValue());
            }
        }
    }
    if(ncases.length>0)
        return ncases[ncases.length-1].second;
    return new ArrayList<>();
}

如果N=s.length()和M=library.size()，这种方法的最坏时间复杂度为O(N*M)。

- Pablo Francisco Pérez Hidalgo

Answer 3

这里是代码（代码本身就很清楚）

public static Collection<String> allPermutations(int num) {
    TreeNode root = createTree(toArray(num));
    Collection<String> result = new ArrayList<String>();
    allLeafNodes(root, result);
    return result;
}

private static Integer[] toArray(int num) {
    ArrayDeque<Integer> array = new ArrayDeque<Integer>();
    do{
        array.push(num % 10);
        num /= 10;
    } while  (num > 0);
    return array.toArray(new Integer[0]);
}

private static TreeNode createTree(Integer[] integers) {
    return doCreateTree(0, "", integers);
}

private static TreeNode doCreateTree(int index, String parentString, Integer[] integers) {
    String nodeData = parentString + AlphabetMatcher.match(index);
    TreeNode root = new TreeNode(nodeData);
    if (integers.length != 0) {

        root.left = doCreateTree(integers[0], nodeData, Arrays.copyOfRange(integers, 1, integers.length));

        if (integers.length > 1) {
            int newIndex = integers[0]* 10 + integers[1];
            root.right = doCreateTree(newIndex, nodeData, Arrays.copyOfRange(integers, 2, integers.length));
        }
    }

    return root;
}

private static void allLeafNodes(TreeNode root, Collection<String> result) {
    if (root != null) {
        if (root.right == null && root.left ==null) {
            result.add(root.data);
        }
        allLeafNodes(root.left, result);
        allLeafNodes(root.right, result);
    }

}

private static class TreeNode {
    private String data;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(String data) {
        this.data = data;
    }
}

private static class AlphabetMatcher {
    private static final String[] alphabet = {"", "a", "b", "c", "d", "e",
            "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r",
            "s", "t", "u", "v", "w", "x", "v", "z"};
    public static String match(int number) {            
        return alphabet[number];
    }
}

这是测试用例

@Test
public void allPermutationsTest() {
    Collection<String> result = StringUtil.allPermutations(1221);
    org.assertj.core.api.Assertions.assertThat(result).hasSize(5).containsAll(Arrays.asList("abba","abu", "ava", "lba", "lu"));

    result = StringUtil.allPermutations(10);
    org.assertj.core.api.Assertions.assertThat(result).hasSize(2).containsAll(Arrays.asList("a","j"));
}

- craftsmannadeem