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

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

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

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

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

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

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

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

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

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

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

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

3. Поменять местами все символы в первой половине строки с соответствующей позицией во второй половине (т.е. i-й символ заменяется на (length-i-1) -й символ).

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

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

Ниже не рассматриваются пары суррогатов 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);
}

Если вы не хотите использовать какие-либо встроенные функции, вам нужно вернуться со строкой к ее составным частям: массиву символов.

Теперь возникает вопрос, как лучше всего перевернуть массив? На практике ответ на этот вопрос также зависит от использования памяти (для очень больших строк), но теоретически эффективность в этих случаях измеряется доступом к массиву.

Самый простой способ - создать новый массив и заполнить его значениями, с которыми вы сталкиваетесь, выполняя итерацию в обратном направлении по исходному массиву и возвращая новый массив. (Хотя с временной переменной вы также можете сделать это без дополнительного массива, как в ответе Саймона Никерсона).

Таким образом, вы получаете доступ к каждому элементу ровно один раз для массива из n элементов. Таким образом, давая эффективность O (n).