Какой самый эффективный алгоритм для обращения строки в Java?

Question

Какой самый эффективный способ перевернуть строку в Java? Должен ли я использовать какой-то оператор XOR? Самый простой способ - поместить все символы в стек и снова поместить их в строку, но я сомневаюсь, что это очень эффективный способ сделать это.

И, пожалуйста, не говорите мне использовать какую-то встроенную функцию в Java. Мне интересно узнать, как это сделать, чтобы не использовать эффективную функцию, но я не знаю, почему она эффективна или как она построена.

Answer 1

Вы говорите, что хотите знать наиболее эффективный способ, и вы не хотите знать какой-то стандартный встроенный способ сделать это. Тогда я говорю вам: RTSL (читай источник, Люк):

Проверьте исходный код AbstractStringBuilder # reverse , который вызывается StringBuilder # reverse. Бьюсь об заклад, он делает некоторые вещи, которые вы бы не рассмотрели для надежной обратной операции.

Answer 2

Следующее не касается суррогатных пар 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 3

Вы сказали, что не хотите делать это простым способом, но для тех, кто гуглит, вы должны использовать StringBuilder.reverse :

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

Если вам нужно реализовать это самостоятельно, переберите символы в обратном порядке и добавьте их в StringBuilder. Вы должны быть осторожны, если есть (или могут быть) суррогатные пары, поскольку их не следует менять на противоположные. Описанный выше метод делает это автоматически, поэтому вам следует использовать его, если это возможно.

Answer 4

Старый пост и вопрос, однако все еще не видел ответов, касающихся рекурсии. Рекурсивный метод, обратный заданной строке s, без ретрансляции на встроенные функции jdk

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

`

Answer 5

Самый быстрый способ - использовать метод reverse() в классах StringBuilder или StringBuffer:)

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

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

Вы также можете запустить половину длины массива и поменять местами символы, проверки, вероятно, замедляют процесс.

Answer 6

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 7

Я не совсем уверен, что вы имеете в виду, когда говорите, что вам нужен эффективный алгоритм.

Я могу придумать способы перестановки строки (все они уже упоминались в других ответах):

1. Используйте стек (ваша идея).

2. Создайте новую перевернутую строку, добавив символы один за другим в обратном порядке от исходной строки к пустой строке / StringBuilder / char [].

3. Обмен всех символов в первой половине строки с соответствующей позицией в последней половине (т. Е. I-й символ заменяется на (length-i-1) -й символ).

Дело в том, что все они имеют одинаковую сложность во время выполнения : O (N). Таким образом, нельзя утверждать, что кто-либо значительно лучше других для очень больших значений N (то есть очень больших строк).

Третий метод имеет одну цель: два других требуют O (N) дополнительного пространства (для стека или новой строки), в то время как он может выполнять перестановки на месте. Но строки являются неизменяемыми в Java, поэтому вам необходимо в любом случае выполнить перестановку во вновь созданном StringBuilder / char [] и, следовательно, в конечном итоге потребуется O (N) дополнительного пространства.

Answer 8

Я думаю, что если у вас ДЕЙСТВИТЕЛЬНО нет проблем с производительностью, вам просто нужно выбрать наиболее читаемое решение:

StringUtils.reverse("Hello World");

Answer 9

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 10

Я бы просто сделал это без использования какой-либо одной функции утилит. Достаточно одного класса String.

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

Проверьте это. Ура !!