reves - invertir una cadena en java recursividad

¿Cuál es la mejor manera de invertir de forma recursiva una cadena en Java?

Question

He estado jugando con la recursividad hoy. A menudo una técnica de programación que no se usa lo suficiente.

Me puse a invertir recursivamente una cuerda. Esto es lo que se me ocurrió:

//A method to reverse a string using recursion
    public String reverseString(String s){
        char c = s.charAt(s.length()-1);
        if(s.length() == 1) return Character.toString(c);   

        return c + reverseString(s.substring(0,s.length()-1));
    }

Mi pregunta: ¿hay una mejor manera en Java?

Answer 1

Capturas la idea básica, pero extraer el último personaje no mejora la claridad. Preferiría lo siguiente, otros podrían no:

public class Foo
{
    public static void main(String[] argv) throws Exception
    {
        System.out.println(reverse("a"));
        System.out.println(reverse("ab"));
        System.out.println(reverse("abc"));
    }


    public final static String reverse(String s)
    {
        // oft-repeated call, so reduce clutter with var
        int length = s.length();

        if (length <= 1)
            return s;
        else
            return s.substring(length - 1) + reverse(s.substring(0, length - 1));
    }
}

Answer 2

Como señaló Mehrdad , es mejor no usar recursividad. Sin embargo, si lo usa, puede conservar el primer y el último caracter de cada llamada, reduciendo a la mitad el número de llamadas recursivas. Es decir,

public String reverseString(String s){
    int len = s.length();

    if (len <= 1) {
        return s;
    }

    char fst = s.charAt(0);
    char lst = s.charAt(len - 1);

    return lst + reverseString(s.substring(1, len - 2)) + fst;
}

Esto también maneja el caso de la cadena vacía. Quizás pasar un StringBuilder con la capacidad adecuada aceleraría aún más las cosas, pero eso queda como un ejercicio para el lector;)

Answer 3

Depende de lo que defina como "mejor". :-) Hablando en serio; su solución utiliza esencialmente la profundidad máxima de recursión; Si el tamaño de la pila es una preocupación para su definición de "mejor", entonces sería mejor que use algo como esto:

public String reverseString(String s) {
   if (s.length() == 1) return s;
   return reverseString(s.substring(s.length() / 2, s.length() -1) + reverseString(0, s.length() / 2);
}

Answer 4

En Java, dado que la cadena es inmutable, la concatenación de cadenas sería más compleja de lo que parece.

Para cada concatenación, crea una nueva cadena copiando el contenido de la Cadena original, lo que resulta en una complejidad lineal O (n) donde n es la longitud de la cadena, entonces para m tales operaciones es O (m * n) , podemos decir es de complejidad cuadrática O (n ^ 2) .

Podemos usar un StringBuilder que tiene una complejidad O (1) para cada apéndice. A continuación se muestra el programa recursivo utilizando StringBuilder. Esto utiliza solo n / 2 fotogramas de pila, por lo que tiene menos complejidad de espacio que la llamada recursiva normal, que sería como s.charAt(s.length-1) + reverse(s.subString(0, s.length-2);

public class StringReverseRecursive {
    public static void main(String[] args) {
        String s = "lasrever gnirts fo noitatnemelpmi evisrucer a si sihT";
        StringBuilder sb = new StringBuilder(s);
        reverse(s, sb, 0, sb.length() - 1);
        System.out.println(sb.toString());
    }

    public static void reverse(String s, StringBuilder sb, int low, int high) {
        if (low > high)
            return;
        sb.setCharAt(low, s.charAt(high));
        sb.setCharAt(high, s.charAt(low));
        reverse(s, sb, ++low, --high);
    }
}

Answer 5

En este contexto, esto es totalmente innecesario, pero puede simular la recursión y evitar problemas de profundidad de recursión si crea su propia pila.

Puede iterar la repetición de la implementación, lo que puede ser necesario cuando tiene algoritmos que son inherentemente recursivos, pero también necesita ejecutarlos para grandes tamaños de problema.

String recIterReverse (String word){

    Stack <String> stack = new Stack <String> ();
    stack.push(word);
    String result = "";

    while (!stack.isEmpty()){
        String temp = stack.pop();
        result = temp.charAt(0) + result;

        if (temp.length() > 1){
        stack.push(temp.substring(1));
        }
    }

    return result;
}

Answer 6

Esa es definitivamente la forma en que iría invirtiendo recursivamente una cuerda (aunque podría ser bueno extenderla al caso de una cuerda vacía en su condición). No creo que haya una forma fundamentalmente mejor.

EDITAR: Puede ser más eficiente operar en una matriz de caracteres y pasar una longitud de "corte" a lo largo de la cadena de recursión, si entiendes mi deriva, en lugar de crear subcadenas. Sin embargo, esto no merece la pena, ya que no es una técnica terriblemente eficiente en primer lugar.

Answer 7

Esta es mi solución, vi en muchas soluciones anteriores que estamos obteniendo la longitud de la cuerda, pero lo ideal es que no la necesitemos. El Zen es usar recursión, simplemente corta el primer carácter de cadena y pasa el resto al método recursivo. ¡¡Hurra!! tenemos la solución.

private static void printReverse(String str) {
            if (!str.isEmpty()) {
                String firstChar = str.substring(0, 1); //Get first char of String
                String newstr = str.substring(0, 0) + str.substring(1); // Get remaining string
                printReverse(newstr); // Recursion magic
                System.out.print(firstChar); //Output
            }
        }

Answer 8

Esto es lo que he encontrado para trabajar y usar recursivo. Puede pasar str.length() como argumento strLength

private static String reverse(String str, int strLength) {
    String result = "";
    if(strLength > 0)
        result = str.charAt(strLength - 1) + reverse(str, strLength - 1);
    return result;
}

Answer 9

La mejor manera es no usar recursividad. Estas cosas se usan generalmente para enseñar a los estudiantes el concepto de recursión, no las mejores prácticas reales. Entonces la forma en que lo haces está bien. Simplemente no use la recursión en Java para este tipo de cosas en aplicaciones del mundo real;)

PD. Aparte de lo que acabo de decir, elegiría "" como el caso base de mi función recursiva:

public String reverseString(String s){
    if (s.length() == 0) 
         return s;

    return reverseString(s.substring(1)) + s.charAt(0);
}

Answer 10

Llamada de función:

    //str:string to be reversed,i=0,j=str.length-1


    public void reverseString(String str,int i,int j)
    {

     if(i==j)
        {
         System.out.println(str);
         return;
        }

     char x=str.charAt(i);
     str=str.replace(str.charAt(i),str.charAt(j));
     str=str.replace(str.charAt(j),x);
     i++;j--;
     reverseString(str,i,j);
    }

este método también funciona ...

Answer 11

No quieres anidar demasiado profundamente. Dividir y vencer es el camino a seguir. También reduce el tamaño total de las cadenas temporales y es susceptible de paralelización.

public static String reverseString(String str) {
    int len = str.length();
    return len<=1 ? str : (
        reverseString(str.substring(len/2))+
        reverseString(str.substring(0, len/2))
    );
}

(No probado - esto es .)

String.concat lugar de + mejoraría el rendimiento a costa de la claridad.

Editar: solo por diversión, una versión amigable de recursión de cola del algoritmo ingenuo.

public static String reverseString(String str) {
    return reverseString("", str);
}
private static String reverseString(String reversed, String forward) {
    return forward.equals("") ? reversed : (
         reverseString(reversed+forward.charAt(0), forward.substring(1)) 
    );
}

El manejo correcto de las parejas sustitutas se deja al lector interesado.

Answer 12

Pruebe lo siguiente:

public class reverse2
{
    public static void main(String name)
    {
    String revname=new StringBuffer(name).reverse().toString();
    System.out.println("original string " + name + " and the reverse of it is " + revname);
    }
}

Answer 13

Puedes probar con una variable externa y agregar 1 por 1 todos los caracteres:

    public static String back="";

public static String reverseString(String str){


    if(str.length()==0){

        return back;

    }else {

        back+=str.charAt(str.length()-1);

        lees(str.substring(0,str.length()-1));


        return back;

    }

}

Answer 14

Reverse String usando la llamada al método recursivo.

Código de muestra

public static String reverseString(String s) {
    if (s.length() == 0) {
        return s;
    }
    else {
        return s.charAt(s.length() - 1) + reverseString(s.substring(0, s.length() - 1));
    }
}

Answer 15

Si crees que menos código es bueno, entonces ...

static String reverse(String str){
    return str.length()>=2 ? str.charAt(str.length()-1) + reverse(str.substring(0,str.length()-1)) : str ;
}

Answer 16

Si está escribiendo código real (no aprendiendo recursión), use el método reverse () de StringBuilder. El Tutorial de Java da este ejemplo:

String palindrome = "Dot saw I was Tod";   
StringBuilder sb = new StringBuilder(palindrome);
sb.reverse();  // reverse it
System.out.println(sb);

Answer 17

Si va a hacer esto, quiere operar en una matriz de caracteres, porque una Cadena es inmutable y va a copiar Cadenas por todas partes si lo hace de esa manera.

Esto no ha sido probado y es una corriente total de consciencia. Probablemente tiene un OB1 en alguna parte. Y muy no-Java.

public String reverseString(String s)
  {
  char[] cstr = s.getChars();
  reverseCStr(cstr, 0, s.length - 1);

  return new String(cstr);
  }

/**
 * Reverse a character array in place.
 */
private void reverseCStr(char[] a, int s, int e)
  {
  // This is the middle of the array; we''re done.
  if (e - s <= 0)
    return;

  char t = a[s];
  a[s] = a[e];
  a[e] = t;
  reverseCStr(a, s + 1, e - 1);
  }

Answer 18

Solo por el gusto de hacerlo, aquí hay un método recursivo de cola que usa StringBuilder (que generalmente se recomienda sobre la manipulación de String s).

public String reverseString(String s_) {
    StringBuilder r = new StringBuilder();
    StringBuilder s = new StringBuilder(s_);
    r = reverseStringHelper(r, s);
    return r.toString();
}
private StringBuilder reverseStringHelper(StringBuilder r, StringBuilder s) {
    if (s.length() == 0)
        return r;
    else
        return reverseStringHelper(r.append(s.charAt(0)), s.deleteCharAt(0));
}

No probado, no he tratado con Java en muchos años, pero esto debería ser correcto.

Answer 19

Ya hay unas 20 respuestas, pero también incluiré mi algoritmo recursivo. Puede ser un poco detallado, pero al menos es legible.

public static String reverseString(String str) {
   return reverseString("", str);
}

private static String reverseString(String result, String original) {
   if (original.length() == 0) {
      return result;
   } else {
      int length = original.length();
      String lastLetter = original.substring(length - 1, length);
      original = original.substring(0, length - 1);
      return reverseString(result + lastLetter, original);
   }
}

El código básicamente toma recursivamente el final de la cadena y la mueve al frente. Por ejemplo, si la cadena que queremos invertir es "jam", cada vez que se llama al método helper, el resultado y las cadenas originales son las siguientes:

// result:  original:
// ""       jam
// m        ja
// ma       j
// maj      ""

Answer 20

aquí está mi función inversa recursiva que está funcionando bien

public static String rev(String instr){
    if(instr.length()<=1){
        return instr;
    } else {
       return (instr.charAt(instr.length()-1)+rev(instr.substring(0,instr.length()-1)) );
    }       
}

Answer 21

Here está mi versión inmutable:

 String reverse(String str) {
    if(str.length()<2) return str;
    return  reverse(str.substring(1)) +str.charAt(0);
}

y la versión recursiva de la cola:

 String reverseTail(String str) {
    if(str.length()<2) return str;
    return str.charAt(str.length()-1)+ reverseTail(str.substring(0,str.length()-1));

Answer 22

String rev="";

public String reverseString(String s){
        if (s.length()==0) return "";
        return rev+s.substring(s.length()-1,s.length())+reverseString(s.substring(0, s.length()-1));
    }

Answer 23

public String reverseString (String s) {

    if (s != null && s.length () > 0 ) {
        rev = rev + s.substring (s.length () - 1);
        reverseString (s.substring (0, s.length () - 1));
    }
    return rev;

}

Answer 24

public class StringUtility {

public static void main(String[] args) {
    StringUtility stringUtility = new StringUtility();

    String input = "santosh123";
    int middle = input.length() / 2;
    middle = middle - 1;
    System.out.println(stringUtility.stringReverse(input, middle));
}

public String stringReverse(String input, int middle) {

    if (middle == -1) {

        System.out.println("if");
        return input;

    } else {

        System.out.println("else");
        input = swapChar(input, middle);
        middle = middle - 1;
        return stringReverse(input, middle);

    }

}

private String swapChar(String input, int middle) {
    StringBuilder str = new StringBuilder(input);
    char begin = str.charAt(middle);
    int endIndex = input.length() - middle - 1;
    char end = str.charAt(endIndex);
    str.setCharAt(middle, end);
    str.setCharAt(endIndex, begin);
    System.out.println(str + "  " + middle + "  " + endIndex);
    return str.toString();
}

}

Answer 25

public static String rev(String name){
    if(name.length()>=1){
    System.out.print(name.charAt(name.length()-1)); 
    return rev(name.substring(0,name.length()-1));
    }
    else{
        return ""+name.substring(0);
    }
}

Answer 26

public static String reverse(String s){

    int n = s.length()-1;

    if(n >=0)
    return  s.substring(s.length()-1)+ReverseString(s.substring(0,n--));
    else return "";
}