The algorithm converts a number to String

Question

I need to develop an algorithm in which each number is encoded in the alphabet, for example:

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

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

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

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

Now here is what I wrote, and I find it ineffective because of a few for loops. Is there a better way to 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 screams for recursion. Here's a quick and dirty implementation that introduces a "number" as a string and uses substring() to use numbers. You can adapt it to use numerical methods to get the first (or first two) decimal digits from an integer if you want.

If you decide to work directly with int , it would be easier to start at the end (working with the least significant digits) than at the beginning - lastDigit = number % 10; otherDigits = number / 10 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 do not think that your solution will find all possible encodings - I think you need some kind of stack to solve it. The solution above implicitly uses the execution stack due to recursive method calls. Another solution might explicitly put objects representing the "todo" calculations in the stack data structure on 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 "debugging println" is usually a bad habit, it would probably be a good exercise to teach these examples with some println() to see how it works.

Answer 2

I think you could split the String in the middle (recursively), find all the combinations in both substrings, and build a cross-product. In order not to miss a single combination, we must also build a cross-product for the two substrings that you get, breaking in the middle with an offset. Something like that:

 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" consists of the following 27 lines: LCABCAW, LCABCLC, ABCLCABC, ABCLCAW, ABCAWLC, AWLCABC, ABCAWAW, ABCAWABC, ABCLCLC, ABCABCABC, LCAWLC, LCAWAW, AWABCLC, LCAWABC, AWABABLC LCLCABLCLC LCABABLC LCABABLC LCABABLC LCABABLC LCABABLC LCABABLC LCABABLC LCABABLC LCLCABABLCLC , AWAWLC, AWAWABC, AWAWAW, ABCABCLC, ABCABCAW, AWLCAW, AWLCLC.

Answer 3

Why not just use the ascii value?

All you have to do is convert the number to String Integer.toString(num) and then run for-loop through .length() into String and pull .charAt(i) from String convert that back to int and then add 16 to him. Then you just need to click on char . So:

 int a = 123; String str = Integer.toString(a); char[] chars = new char[str.length()]; for(int i=0,n=str.length();i<n;i++){ chars[i] = (char)(str.charAt(i)+16); } String message = String.valueOf(chars); 

Answer 4

This problem can be solved in o (fib (n + 2)) time with the standard DP algorithm. We have exactly n additional tasks and a button, we can solve every problem in o (fib (i)) time. Summation of the series gives fib (n + 2).

If you carefully consider the issue, you will see that this is a series of fibonacci. I took the standard code and slightly changed it to suit our conditions.

The space is obviously related to the size of all solutions o (fib (n)).

Consider this code:

 Map<Integer, String> mapping = new HashMap<Integer, String>(); List<String > iterative_fib_sequence(int input) { int length = Math.floor(Math.log10(Math.abs(input))) + 1; if (length <= 1) { if (length==0) { return ""; } else//input is aj { return mapping.get(input); } } List<String> b = new List<String>(); List<String> a = new List<String>(mapping.get(input.substring(0,0)); List<String> c = new List<String>(); for (int i = 1; i < length; ++i) { int dig2Prefix = input.substring(i-1, i); //Get a letter with 2 digit (kz) if (mapping.contains(dig2Prefix)) { String word2Prefix = mapping.get(dig2Prefix); foreach (String s in b) { c.Add(s.append(word2Prefix)); } } int dig1Prefix = input.substring(i, i); //Get a letter with 1 digit (aj) String word1Prefix = mapping.get(dig1Prefix); foreach (String s in a) { c.Add(s.append(word1Prefix)); } b = a; a = c; c = new List<String>(); } return a; }