Algorithm translate a number to String [closed]

Question

I need to design an algorithm where each number is encoded to an alphabet, for example:

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

Given a set of numbers, I have to translate them to a combination of strings. For example:

123 can be translated to - ABC(123), AW(1 23) and LC(12 3)

Write an algorithm to find the combinations for number - 123123123.

Now here is what I wrote and I find it inefficient because of multiple "for" loops. Is there any better way I can rewrite this algorithm?

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();
    }

}

For '123' - [ABC, AW, LC]

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

Answer 1

This problem is crying out for recursion. Here's a quick and dirty implementation that takes the input "number" in as a string and uses substring() to consume the digits. You could adapt it to use numerical methods to get the first (or first two) decimal digits from an integer if you prefer.

If you choose to work directly from an int, it would probably be easier to start at the end (working with the least-significant-digits) than at the beginning -- 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);
}

I don't think your solution will find all possible encodings -- I think you need some sort of stack to solve it. The solution above implicitly uses the execution stack, because of recursive method calls. Another solution could explicitly place objects representing "todo" calculations onto a stack data structure in the heap:

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)));
        }
    }
}

Although "println debugging" is generally a bad habit, it would probably be a good learning exercise to run these examples with some println()s to observe how it works.

Answer 2

I think you could split the String in the middle (recursively), search for all combinations in both substrings and build the cross product. To not miss any combinations we have to also build the cross product for the two substrings you get by splitting in the middle with an offset of one. Something like this:

private static int[] values;

public static final Set<String> solve(String s) {
    values = new int[s.length()];
    for (int i = 0; i < values.length; i++)
        values[i] = s.charAt(i) - '0';
    return solve(0, values.length);
}

private static final Set<String> solve(int start, int len) {
    Set<String> ret = new HashSet<>();
    if (len == 1) {
        ret.add("" + ((char)(values[start] - 1 + 'A')));
    } else if (len == 2) {
        ret.add("" + ((char)(values[start] - 1 + 'A')) + 
                     ((char)(values[start + 1] - 1 + 'A')));
        int n = values[start] * 10 + values[start + 1];
        if (n <= 26)
            ret.add("" + ((char)(n - 1 + 'A')));
    } else {
        int next = start + len / 2;
        cross(solve(start, next - start), solve(next, start + len - next), ret);
        cross(solve(start, next - start + 1), solve(next + 1, start + len - next - 1), ret);
    }
    return ret;
}

private static final void cross(Set<String> a, Set<String> b, Set<String> target) {
    for (Iterator<String> itr = a.iterator(); itr.hasNext();) {
        String s = itr.next();
        for (Iterator<String> itr2 = b.iterator(); itr2.hasNext();) {
            target.add(s + itr2.next());
        }
    }
}

Btw. the solution for "123123123" are the following 27 strings: LCABCAW, LCABCLC, ABCLCABC, ABCLCAW, ABCAWLC, AWLCABC, ABCAWAW, ABCAWABC, ABCLCLC, ABCABCABC, LCAWLC, LCAWAW, AWABCLC, LCAWABC, AWABCAW, LCLCAW, AWABCABC, LCLCLC, LCLCABC, LCABCABC, AWAWLC, AWAWABC, AWAWAW, ABCABCLC, ABCABCAW, AWLCAW, AWLCLC.