Invertir cadenas en Java: aprender a invertir cadenas de diferentes maneras

¿Es posible llegar a ser un buen programador sin conocer algoritmos? Muy, muy controvertido. Sí, puedes encontrar trabajo en nuestras empresas de subcontratación, porque durante las entrevistas hacen preguntas principalmente sobre tecnología. ¿Pero serás un buen especialista si tus decisiones están llenas de muletas? Si desea mudarse a una empresa extranjera más seria, encontrará entrevistas que se centran principalmente en algoritmos. De una forma u otra, vale la pena adoptar los algoritmos más básicos, porque un algoritmo es amigo del programador . Hoy tocaremos uno de estos temas y discutiremos formas de invertir una cadena. Aquí todo es sencillo. Invertir una cuerda es hacer que la cuerda se invierta. Por ejemplo: JavaRush para siempre ->reverof hsuRavaJ Entonces, ¿cómo se puede invertir una cadena en Java?

1. Constructor de cadenas/Buffer de cadenas

La forma más común y sencilla es utilizar StringBuilder/StringBuffer :

public static String reverseString(String str) {
  return new StringBuilder(str).reverse().toString();
}

Mejor solución = más simple. Cuando se nos pregunta cómo invertir una cadena en Java, esto es lo primero que nos viene a la mente. Pero ya hablamos de algoritmos antes, ¿no? Echemos un vistazo a las soluciones que no están listas para usar.

2. Solución de matriz

public static String reverseString(String str) {
  char[] array = str.toCharArray();
  String result = "";
  for (int i = array.length - 1; i >= 0; i--) {
     result = result + array[i];
  }
  return result;
}

Convertimos nuestra cadena en una matriz usando el método toCharArray . Ejecutemos un bucle for a través de esta matriz desde su final, agregando caracteres a la cadena resultante a lo largo del camino.

3. Solución con charAt

public static String reverseString(String str) {
  String result = "";
  for (int i = 0; i < str.length(); i++) {
     result = str.charAt(i) + result;
  }
  return result;
}

En este caso, ni siquiera tenemos que dividir la cadena en una matriz, ya que extraemos cada carácter usando el método de la clase String - charAt (el bucle for, nuevamente, es inverso, lo que nos permite tomar caracteres secuencialmente hacia atrás).

4. Solución con Stack

Nadie ha estado usando la clase Stack durante mucho tiempo y se considera obsoleta, pero aún así, como referencia, será útil buscar una solución que la use:

public static String reverseString(String str) {
  Stack<Character> stack = new Stack<>();
  String result = "";
  for (Character character : str.toCharArray()) {
     stack.add(character);
  }
  while (!stack.isEmpty()) {
     result = result + stack.pop();
  }
  return result;
}

Aquí nuevamente usamos toCharArray para dividir la cadena en una matriz y ponerlo todo en nuestra Pila con un tipo genérico Character . A continuación, comenzamos a tomar elementos de la parte superior de la pila. Debido a la naturaleza de la pila como estructura LIFO : último en entrar , primero en salir (primero en entrar, último en salir), los elementos se tomarán hacia atrás y el resultado se almacenará en la fila resultante.

5. Solución por recursividad

Casi todos los problemas de algoritmos se pueden resolver mediante recursividad. Y aquí tampoco podemos prescindir de ella. O incluso sin ellos. Después de todo, hoy consideraremos no solo un método para resolver la recursividad, sino varios.

• método uno

  public static String reverseString(String str) {
    String rightStr;
    String leftStr;
    int length = str.length();
  
    if (length <= 1) {
       return str;
    }
  
    leftStr = str.substring(0, length / 2);
    rightStr = str.substring(length / 2, length);
  
    return reverseString(rightStr) + reverseString(leftStr);
  }

  Usamos las variables rightStr y leftStr para dividir la cadena entrante en dos partes iguales. Luego, usando esta división, dividimos la cadena en las partes divisibles más pequeñas (1 carácter). Después la recursividad comienza a colapsar, regresando los caracteres en orden inverso (los que estaban a la derecha se colocaron a la izquierda; los que estaban a la izquierda se colocaron a la derecha)

  No debemos olvidar que cada recursión es una llamada múltiple a un método y, como resultado, un gasto considerable de recursos. Bueno, si hablamos de recursividad con una condición de salida inalcanzable, entonces este es el camino al infinito y al StackOverflowError.

• método dos

  Aquí necesitamos un argumento adicional en el método: índice.

  Cuando se ejecuta este método, se le asigna una longitud de cadena de -1:

  String str = "JavaRush forever";
  System.out.println(reverseString(str, str.length()-1));

  Y el método en sí:

  public static String reverseString(String str, int index) {
    if(index == 0){
       return str.charAt(0) + "";
    }
  
    char letter = str.charAt(index);
    return letter + reverseString(str, index-1);
  }

  Nuestro índice sirve como indicador de qué elemento de fila usaremos ahora (y usaremos los elementos del final).

  Por lo tanto, establecemos condiciones de salida cuando el índice llega al primer elemento.

Sumamos los valores obtenidos mediante el índice de letras con el resultado de la ejecución anterior del método y devolvemos el resultado.

• método tres

  public static String reverseString(String str) {
    if (str.length() <= 1) {
       return str;
    }
    return reverseString(str.substring(1)) + str.charAt(0);
  }

  Este método es esencialmente el más simple de los recursivos. Y como recordamos, simple = mejor.

  Durante cada ejecución, especificamos la misma cadena, pero sin el primer elemento. Cuando se alcanza la condición de salida (cuando nos queda un carácter), la recursividad comienza a colapsar y el carácter anterior no utilizado se agregará a cada resultado posterior.

6. Usando XOR

XOR es una operación lógica bit a bit. En el caso de dos variables, el resultado de una operación es verdadero si y sólo si uno de los argumentos es verdadero y el otro es falso. Puede leer más sobre las operaciones bit a bit en este artículo . La siguiente solución dependerá del hecho de que:

(A XOR B) XOR B = A
(A XOR B) XOR A = B

Cómo se verá el método:

public static String reverseString(String str) {
  char[] arr = str.toCharArray();
  int low = 0;
  int high = arr.length - 1;
  String result = "";
  while (low < high) {
     arr[low] = (char) (arr[low] ^ arr[high]);
     arr[high] = (char) (arr[low] ^ arr[high]);
     arr[low] = (char) (arr[low] ^ arr[high]);
     low++;
     high--;
  }
  for (int i = 0; i < arr.length; i++) {
     result = result + arr[i];
  }
  return result;
}

Averigüemos qué está pasando aquí. Creamos una matriz a partir de la cadena entrante. Creamos dos variables, baja y alta , que almacenan índices para atravesar la matriz. En consecuencia, uno se moverá de principio a fin (le damos el valor 0, el segundo) de final a principio, le asignamos arr.length - 1 . Entramos en un bucle que se reproducirá siempre que el índice máximo sea mayor que el mínimo . Aquí es donde empiezan a suceder las cosas divertidas: el uso del OR exclusivo. Veamos xey como ejemplo . Supongamos que arr[alto] = 'x'; Su código binario será 1 1 1 1 0 0 0 En este momento arr[high] = 'n'; Código binario - 1 1 0 1 1 1 0 Lo que tendremos en operaciones XOR en bucle:

1. arr[bajo] = (char) (arr[bajo] ^ arr[alto]);

   
   arr[low] = 1 1 0 1 1 1 0
   arr[high] =1 1 1 1 0 0 0
   arr[low] = 0 0 1 0 1 1 0

2. arr[alto] = (char) (arr[bajo] ^ arr[alto]);

   
   arr[low] =  0 0 1 0 1 1 0
   arr[high] = 1 1 1 1 0 0 0
   arr[high] = 1 1 0 1 1 1 0

3. arr[bajo] = (char) (arr[bajo] ^ arr[alto]);

   
   arr[low] =  0 0 1 0 1 1 0
   arr[high] = 1 1 0 1 1 1 0
   arr[low] =  1 1 1 1 0 0 0

Como resultado, gracias a estas operaciones, intercambiamos los valores de dos celdas de la matriz. arr[high] tiene tantos elementos desde el final de la matriz como arr[low] desde el principio. Por lo tanto, simplemente intercambiamos los elementos con estos índices. Por ejemplo, en la primera ejecución de la oración "JavaRush para siempre" se intercambiarán J y r , en la segunda - a y e , etc. Si tenemos un número impar de caracteres, cuando lleguemos al elemento que está en el medio, seremos expulsados ​​del bucle (es decir, no es necesario cambiar el elemento del medio). Si es par, seremos expulsados ​​después de procesar todos los elementos. Bueno, después de eso entramos en un bucle normal y construimos una cadena a partir de los elementos de la matriz.