Каков наилучший способ рекурсивного обращения строки в 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

Лучший способ - не использовать рекурсию. Эти вещи обычно используются, чтобы научить студентов концепции рекурсии, а не фактическим лучшим практикам. То, как вы это делаете, просто прекрасно. Только не используйте рекурсию в Java для подобных вещей в реальных приложениях;)

PS. Помимо того, что я только что сказал, я бы выбрал "" в качестве базового случая моей рекурсивной функции:

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

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

Answer 2

Если вы собираетесь это сделать, вы хотите работать с массивом символов, потому что строка является неизменной, и вы будете копировать строки везде, если вы сделаете это таким образом.

Это непроверенный и полностью поток сознания. Вероятно, где-то есть OB1. И очень не-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 3

Вы не хотите вкладывать слишком глубоко. Разделяй и властвуй - это путь. Также уменьшает общий размер временных строк и поддается распараллеливанию.

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

(не проверено - это переполнение стека).

String.concat вместо + улучшит производительность за счет ясности.

Редактировать: просто для удовольствия, дружественная к хвосту версия рекурсивного алгоритма.

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

Правильная обработка суррогатных пар оставлена ​​заинтересованному читателю.

Answer 4

вот моя рекурсивная обратная функция, которая работает нормально

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 5

Просто, черт возьми, вот хвост-рекурсивный метод с использованием StringBuilder (который обычно рекомендуется вместо манипулирования String с).

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

Не проверено, я много лет не имел дело с Java, но это должно быть правильно.

Answer 6

Если вы пишете реальный код (не изучая рекурсию), используйте метод reverse () StringBuilder. Java Tutorial дает этот пример:

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

Answer 7

Это зависит от того, что вы определяете как «лучше». :-) Если серьезно; ваше решение по существу использует максимальную глубину рекурсии; если размер стека важен для вашего определения «лучше», то вам лучше использовать что-то вроде этого:

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 8

В Java, поскольку String является неизменным, конкатенация String будет более сложной, чем кажется.

Для каждой конкатенации создается новая строка, копирующая содержимое исходной строки, что приводит к линейной сложности O (n) , где n - длина строки, поэтому для m таких операций это O (m * n) , можно сказать, что оно имеет квадратичную сложность O (n ^ 2) .

Мы можем использовать StringBuilder, который имеет O (1) сложность для каждого добавления. Ниже приведена рекурсивная программа, использующая StringBuilder. При этом используются только n / 2 стековых фрейма, поэтому он имеет меньшую сложность пространства, чем обычный рекурсивный вызов, который будет выглядеть как 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 9

Это то, что я нашел для работы и рекурсивного использования. Вы можете передать str.length() в качестве аргумента 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 10

Обратная строка с использованием рекурсивного вызова метода.

Пример кода

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