reves - ¿Cuál es el algoritmo más eficiente para invertir una cadena en Java?

invertir una cadena en java recursividad

Question

¿Cuál es la forma más eficiente de invertir una cadena en Java? ¿Debo usar algún tipo de operador xor? La manera más fácil sería poner todos los caracteres en una pila y volver a ponerlos en una cadena, pero dudo que sea una forma muy eficiente de hacerlo.

Y por favor no me diga que use alguna función incorporada en Java. Estoy interesado en aprender cómo hacerlo, no para utilizar una función eficiente, pero sin saber por qué es eficiente o cómo se desarrolla.

Answer 1

Creo que si REALMENTE no tiene problemas de rendimiento, debería ir con la solución más legible, que es:

StringUtils.reverse("Hello World");

Answer 2

Dijiste que no querías hacerlo de la manera fácil, pero para aquellos en Google debes usar StringBuilder.reverse :

String reversed = new StringBuilder(s).reverse().toString();

Si necesita implementarlo usted mismo, repita los caracteres en orden inverso y añádalos a un StringBuilder. Debe tener cuidado si hay (o puede haber) pares suplentes, ya que estos no deben revertirse. El método que se muestra arriba lo hace automáticamente, por lo que debe usarlo si es posible.

Answer 3

La manera más rápida sería usar el método reverse() en las clases StringBuilder o StringBuffer :)

Si quiere implementarlo usted mismo, puede obtener la matriz de caracteres, asignar una segunda matriz de caracteres y mover los caracteres, en pseudo código esto sería como:

String reverse(String str) {
    char[] c = str.getCharArray
    char[] r = new char[c.length];
    int    end = c.length - 1

    for (int n = 0; n <= end; n++) {
        r[n] = c[end - n];
    }

    return new String(r);
}

También podría ejecutar la mitad de la longitud de la matriz y cambiar los caracteres, los controles implicados ralentizan las cosas probablemente.

Answer 4

Lo siguiente no trata con los pares sustituto UTF-16.

public static String reverse(String orig)
{
    char[] s = orig.toCharArray();
    int n = s.length;
    int halfLength = n / 2;
    for (int i=0; i<halfLength; i++)
    {
        char temp = s[i];
        s[i] = s[n-1-i];
        s[n-1-i] = temp;
    }
    return new String(s);
}

Answer 5

No estoy seguro de a qué te refieres cuando dices que necesitas un algoritmo eficiente .

Las formas de invertir una cadena que puedo pensar son (ya se mencionan en otras respuestas):

1. Usa una pila (tu idea).

2. Cree una nueva Cadena invertida agregando caracteres uno por uno en orden inverso desde la Cadena original a una Cadena / StringBuilder / char [] en blanco.

3. Intercambia todos los caracteres en la primera mitad de la Cadena con su posición correspondiente en la última mitad (es decir, el i-ésimo carácter se intercambia con el carácter (longitud-i-1) ésimo).

La cuestión es que todos ellos tienen la misma complejidad de tiempo de ejecución : O (N). Por lo tanto, no se puede argumentar que cualquiera sea significativamente mejor que los demás para valores muy grandes de N (es decir, cadenas muy grandes).

El tercer método tiene una cosa a su favor, los otros dos requieren O (N) espacio extra (para la pila o la nueva Cadena), mientras que puede realizar intercambios en su lugar. Pero las cadenas son inmutables en Java, por lo que es necesario realizar intercambios en un StringBuilder / char [] creado recientemente y, por lo tanto, terminar necesitando O (N) espacio adicional.

Answer 6

Si no desea utilizar ninguna función incorporada, debe volver con la cadena a sus partes componentes: una matriz de caracteres.

Ahora la pregunta es ¿cuál es la forma más eficiente de invertir una matriz? La respuesta a esta pregunta en la práctica también depende del uso de la memoria (para cadenas muy grandes), pero en teoría la eficiencia en estos casos se mide en los accesos de matriz.

La forma más fácil es crear una nueva matriz y llenarla con los valores que encuentre mientras itera de forma inversa sobre la matriz original y devuelve la nueva matriz. (Aunque con una variable temporal también podría hacer esto sin una matriz adicional, como en la respuesta de Simon Nickersons).

De esta forma, accede a cada elemento exactamente una vez para una matriz con n elementos. Dando así una eficacia de O (n).

Answer 7

Simplemente lo haría de esta manera sin el uso de una sola función de utilidad. Solo la clase String es suficiente.

public class MyStringUtil {

    public static void main(String[] args) {
        String reversedString = reverse("StringToReverse");
        System.out.println("Reversed String : " + reversedString);
    }

    /**
     * Reverses the given string and returns reversed string
     * 
     * @param s Input String
     * @returns reversed string
     */
    private static String reverse(String s) {
        char[] charArray = s.toCharArray(); // Returns the String''s internal character array copy
        int j = charArray.length - 1;
        for (int i = 0; charArray.length > 0 && i < j; i++, j--) {
            char ch = charArray[i];
            charArray[i] = charArray[j];
            charArray[j] = ch;
        }
        return charArray.toString();
    }
}

Revisalo. ¡¡Aclamaciones!!

Answer 8

Una publicación y una pregunta antiguas, sin embargo, todavía no se encontraron respuestas relacionadas con la recursión. El método recursivo revierte las cadenas dadas, sin retransmitir las funciones jdk incorporadas

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

`

Answer 9

Una variante puede ser, intercambiando los elementos.

int n = length - 1;
char []strArray = str.toCharArray();
for (int j = 0; j < n; j++) {
   char temp = strArray[j];
   char temp2 = strArray[n];
   strArray[j] = temp2;
   strArray[n] = temp;
   n--;
  }

Answer 10

Usando String:

String abc = "abcd";
int a= abc.length();

String reverse="";

for (int i=a-1;i>=0 ;i--)
{
    reverse= reverse + abc.charAt(i);
}
System.out.println("Reverse of String abcd using invert array is :"+reverse);

Usando StringBuilder:

    String abc = "abcd";
    int a= abc.length();
    StringBuilder sb1 = new StringBuilder();

    for (int i=a-1;i>=0 ;i--)
    {
        sb1= sb1.append(abc.charAt(i));
    }
    System.out.println("Reverse of String abcd using StringBuilder is :"+sb1);

Answer 11

Usando múltiples hilos para intercambiar los elementos:

    final char[] strArray = str.toCharArray();

    IntStream.range(0, str.length() / 2).parallel().forEach(e -> {
        final char tmp = strArray[e];
        strArray[e] = strArray[str.length() - e - 1];
        strArray[str.length() - e - 1] = tmp;
    });
    return new String(strArray);

Answer 12

Usted dice que quiere saber de la manera más eficiente y que no desea conocer una forma estándar incorporada de hacerlo. Entonces te digo: RTSL (leer la fuente, luke):

Echa un vistazo al código fuente de AbstractStringBuilder#reverse , que se llama por StringBuilder # reverse. Apuesto a que hace algunas cosas que no habrías considerado para una operación inversa robusta.

Answer 13

char* rev(char* str)
    {
    int end= strlen(str)-1;
    int start = 0;

    while( start<end )
    {
    str[start] ^= str[end];
    str[end] ^= str[start];
    str[start]^= str[end];

    ++start;
    --end;
    }

    return str;
}

======================

¿Te preguntas cómo funciona?

Primera operación:

x1 = x1 XOR x2

x1: 1   0   0
x2: 1   1   1
New x1: 0   1   1

Segunda operación

x2 = x2 XOR x1

x1: 0   1   1
x2: 1   1   1
New x2: 1   0   0
//Notice that X2 has become X1 now

Tercera operación:

x1 = x1 XOR x2
x1: 0   1   1
x2: 1   0   0
New x1: 1   1   1
//Notice that X1 became X2

Answer 14

private static String reverse(String str) {
    int i = 0;
    int j = str.length()-1;
    char []c = str.toCharArray();
    while(i <= j){
        char t = str.charAt(i);
        c[i] = str.charAt(j);
        c[j]=t;
        i++;
        j--;
    }
    return new String(c);
}

Answer 15

public class ReverseInPlace {

  static char[]  str=null;

    public static void main(String s[]) {
      if(s.length==0)
        System.exit(-1);

       str=s[0].toCharArray();

       int begin=0;
       int end=str.length-1;

       System.out.print("Original string=");
       for(int i=0; i<str.length; i++){
         System.out.print(str[i]);
       }

       while(begin<end){
          str[begin]= (char) (str[begin]^str[end]);
          str[end]= (char)   (str[begin]^str[end]);
          str[begin]= (char) (str[end]^str[begin]);

          begin++;
          end--;       
       }

       System.out.print("/n" + "Reversed string=");
       for(int i=0; i<str.length; i++){
         System.out.print(str[i]);
       }

    }
}

Answer 16

public static String Reverse(String word){
        String temp = "";
        char[] arr = word.toCharArray();
        for(int i = arr.length-1;i>=0;i--){
            temp = temp+arr[i];
        }
        return temp;
    }

Answer 17

public static String reverseString(String str)
{
    StringBuilder sb = new StringBuilder();

    for (int i = str.length() - 1; i >= 0; i--)
    {
        sb.append(str[i]);
    }

    return sb.toString();
}

Answer 18

public static string getReverse(string str)
{
    char[] ch = str.ToCharArray();
    string reverse = "";
    for (int i = str.Length - 1; i > -1; i--)
    {
        reverse += ch[i];
    }
    return reverse;
}

//using in-built method reverse of Array
public static string getReverseUsingBulidingFunction(string str)
{
    char[] s = str.ToCharArray();
    Array.Reverse(s);
    return new string(s);
}


public static void Main(string[] args)
{
    string str = "123";
    Console.WriteLine("The reverse string of ''{0}'' is: {1}",str,getReverse(str));
    Console.WriteLine("The reverse string of ''{0}'' is: {1}", str, getReverseUsingBulidingFunction(str));
    Console.ReadLine();
}

Answer 19

public static void main(String[] args){
    String string ="abcdefghijklmnopqrstuvwxyz";
    StringBuilder sb = new StringBuilder(string);
    sb.reverse();

    System.out.println(sb);
}