算法将数字转换为String

Question

我需要设计一种算法,其中每个数字都被编码为字母表,例如:

1 = A,2 = B,3 = C ... 26 = Z

给定一组数字,我必须将它们转换为字符串组合.例如:

123可以被翻译为 - ABC(123),AW(1 23)和LC(12 3)

编写算法以查找数字组合 - 123123123.

现在这就是我写的内容,因为有多个"for"循环,我发现它效率低下.有没有更好的方法可以重写这个算法？

public class ValidCombinations {
    Map<Integer, String> mapping = new HashMap<Integer, String>();

    public void run() {
            String s = "123123123";

            /*Convert String to int[]*/
            char[] cArray = s.toCharArray();
            int[] input = new int[cArray.length];

            for (int i=0; i<cArray.length; i++) {
                    input[i] = Character.getNumericValue(cArray[i]);
            }

            Set<String> output = new HashSet<String>();

            for (int i='A'; i<='Z'; i++) {
                    mapping.put(i - 'A' + 1, String.valueOf((char)i));
            }

            for (int i=0; i<input.length; i++) {
                    if (mapping.containsKey(input[i])) {
                            output.add(precombine(i, input) + mapping.get(input[i]) + postcombine(i, input));
                            if (i+1<input.length) {
                                    if (mapping.containsKey(input[i]*10 + input[i+1])) {
                                            output.add(precombine(i, input) + mapping.get(input[i]*10 + input[i+1]) + postcombine(i+1, input));
                                    }
                            }
                    }
            }

            System.out.println(output);
    }

    public String precombine(int i, int[] input) {
            String residue="";

            for (int m=0; m<i; m++) {
                    residue += mapping.get(input[m]);
            }

            return residue;
    }

    public String postcombine(int i, int[] input) {
            String residue="";

            for (int k=i+1; k<input.length; k++) {
                    residue += mapping.get(input[k]);
            }

            return residue;
    }

    public static void main(String[] args) {
            ValidCombinations v = new ValidCombinations();
            v.run();
    }

}

对于'123' - [ABC,AW,LC]

对于'123123123' - [LCABCABC,AWABCABC,ABCAWABC,ABCLCABC,ABCABCLC,ABCABCABC,ABCABCAW]

Answer 1

这个问题迫切需要递归.这是一个快速而又脏的实现,它将输入"number"作为字符串并用于使用substring()数字.如果您愿意,可以调整它以使用数值方法从整数中获取第一个(或前两个)十进制数字.

如果你选择直接从a int开始工作,最后开始(使用最低有效位数)可能比开始时更容易 -lastDigit = number % 10; otherDigits = number / 10

public List<String> encodings(String number) {
    List<String> out = new ArrayList<>();
    addEncodings("", number, out);
    return out;
}

private void addEncodings(String prefix, String number, List<String> out) {
    if (number.length() == 0) {
        out.add(prefix);
    } else {
        addParsingNDigits(1, prefix, number, out);
        addParsingNDigits(2, prefix, number, out);
    }

}

private void addParsingNDigits(int digits, String prefix, String number, List<String> out) {
    if (number.length() >= digits) {
        char encodedChar = parseChars(number, digits);
        if (encodedChar >= 'A' && encodedChar <= 'Z') {
            addEncodings(prefix + encodedChar, number.substring(digits), out);
        }
    }
}

private char parseChars(String number, int length) {
    int intVal = Integer.parseInt(number.substring(0, length));
    return (char) ('A' + intVal - 1);
}

我不认为你的解决方案会找到所有可能的编码 - 我认为你需要某种堆栈来解决它.由于递归方法调用,上面的解决方案隐式使用执行堆栈.另一个解决方案可以明确地将表示"todo"计算的对象放到堆中的堆栈数据结构中:

private static class StackItem {

    public StackItem(String prefix, String number) {
        this.prefix = prefix;
        this.number = number;
    }

    public String prefix;
    public String number;
}

public List<String> encodings(String number) {
    List<String> results = new ArrayList<>();
    Stack<StackItem> stack = new Stack<>();
    stack.push(new StackItem("", number));
    while (!stack.isEmpty()) {
        StackItem current = stack.pop();
        if (current.number.equals("")) {
            results.add(current.prefix);
        } else {
            addToStackTakingNChars(2, current, stack);
            addToStackTakingNChars(1, current, stack);
        }
    }
    return results;
}

private void addToStackTakingNChars(int n, StackItem current, Stack<StackItem> stack) {
    if (current.number.length() >= n) {
        char c = parseChars(current.number, n);
        if (c >= 'A' && c <= 'Z') {
            stack.push(new StackItem(current.prefix + c, current.number.substring(n)));
        }
    }
}

虽然"println调试"通常是一个坏习惯,但用一些println()s来运行这些例子来观察它是如何工作的可能是一个很好的学习练习.