Каков наилучший способ рекурсивного обращения строки в Java?

Question

Я сегодня возился с рекурсией. Часто методика программирования используется недостаточно.

Я решил рекурсивно перевернуть строку. Вот что я придумал:

//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));
    }

Мой вопрос: есть ли лучший способ в Java?

Answer 1

Как заметил Мехрдад , лучше не использовать рекурсию. Однако, если вы его используете, вы также можете сохранять как первый, так и последний символ каждого вызова, таким образом вдвое уменьшая количество рекурсивных вызовов. То есть

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;
}

Это также обрабатывает случай пустой строки. Возможно, передача StringBuilder с соответствующей емкостью ускорит процесс, но это остается для читателя в качестве упражнения;)

Answer 2

Здесь - моя неизменная версия:

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

и хвостовая рекурсивная версия:

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

Answer 3

Это мое решение, я видел, что во многих решениях выше мы получаем длину строки, но в идеале нам это не нужно. Дзен должен использовать рекурсию, просто нарезать первый символ строки и передать остаток рекурсивному методу. Ура!! мы получили решение.

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 4

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 5

вызов функции:

    //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);
    }

этот метод тоже работает ..

Answer 6

Вы фиксируете основную идею, но извлечение последнего символа не улучшает ясность. Я бы предпочел следующее, другие не могут:

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));
    }
}