Necesito diseñar un algoritmo donde cada número esté codificado en un alfabeto, por ejemplo:
1=A, 2=B, 3=C...26=Z
Dado un conjunto de números, tengo que traducirlos a una combinación de cadenas. Por ejemplo:
123 se puede traducir a - ABC(123), AW(1 23) y LC(12 3)
Escribe un algoritmo para encontrar las combinaciones para el número - 123123123.
Ahora, aquí está lo que escribí y lo encuentro ineficiente debido a múltiples bucles "for". ¿Hay alguna forma mejor de reescribir este algoritmo?
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(); }}
Para '123' - [ABC, AW, LC]
Para '123123123' - [LCABCABC, AWABCABC, ABCAWABC, ABCLCABC, ABCABCLC, ABCABCABC, ABCABCAW]
Este problema está pidiendo a gritos recursividad. Aquí hay una implementación rápida y sucia que toma el "número" de entrada como una cadena y usa substring() para consumir los dígitos. Si lo prefiere, puede adaptarlo para usar métodos numéricos para obtener los primeros (o los dos primeros) dígitos decimales de un número entero.
Si elige trabajar directamente desde un int , probablemente sería más fácil comenzar al final (trabajando con los dígitos menos significativos) que al principio -- 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); }No creo que su solución encuentre todas las codificaciones posibles; creo que necesita algún tipo de pila para resolverlo. La solución anterior utiliza implícitamente la pila de ejecución, debido a las llamadas a métodos recursivos. Otra solución podría colocar explícitamente objetos que representen cálculos "todo" en una estructura de datos de pila en el montón:
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))); } } } Aunque la "depuración de println" es generalmente un mal hábito, probablemente sería un buen ejercicio de aprendizaje ejecutar estos ejemplos con algunos println() s para observar cómo funciona.
Creo que podría dividir la Cadena en el medio (recursivamente), buscar todas las combinaciones en ambas subcadenas y construir el producto cruzado. Para no perder ninguna combinación, también tenemos que construir el producto cruzado para las dos subcadenas que obtienes dividiendo en el medio con una compensación de uno. Algo como esto:
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()); } } }Por cierto. la solución para "123123123" son las siguientes 27 cadenas: 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.
¿Por qué no usar simplemente el valor ascii?
Todo lo que tendría que hacer sería convertir el número a un String Integer.toString(num) y luego ejecutar un for-loop través de .length() de String y extraer el .charAt(i) de String convert eso vuelve a un int y luego súmale 16. Entonces solo necesitarías lanzar a un char . al igual que:
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);