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

Question

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

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

Answer 1

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

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

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

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

Answer 2

char* rev(char* str)
    {
    int end= strlen(str)-1;
    int start = 0;

    while( start<end )
    {
    str[start] ^= str[end];
    str[end] ^= str[start];
    str[start]^= str[end];

    ++start;
    --end;
    }

    return str;
}

=========================

Хотите знать, как это работает?

Первая операция:

x1 = x1 XOR x2

x1: 1   0   0
x2: 1   1   1
New x1: 0   1   1

Вторая операция

x2 = x2 XOR x1

x1: 0   1   1
x2: 1   1   1
New x2: 1   0   0
//Notice that X2 has become X1 now

Третья операция:

x1 = x1 XOR x2
x1: 0   1   1
x2: 1   0   0
New x1: 1   1   1
//Notice that X1 became X2

Answer 3

public static String Reverse(String word){
        String temp = "";
        char[] arr = word.toCharArray();
        for(int i = arr.length-1;i>=0;i--){
            temp = temp+arr[i];
        }
        return temp;
    }

Answer 4

Конечно, это самый эффективный способ:

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

Но если вам не нравится это, я рекомендую это:

public String reverseString(String str)
{
    String output = "";
    int len = str.length();
    for(int k = 1; k <= str.length(); k++, len--)
    {
        output += str.substring(len-1,len);
    }
    return output;
}

Answer 5

public static string getReverse(string str)
{
    char[] ch = str.ToCharArray();
    string reverse = "";
    for (int i = str.Length - 1; i > -1; i--)
    {
        reverse += ch[i];
    }
    return reverse;
}

//using in-built method reverse of Array
public static string getReverseUsingBulidingFunction(string str)
{
    char[] s = str.ToCharArray();
    Array.Reverse(s);
    return new string(s);
}


public static void Main(string[] args)
{
    string str = "123";
    Console.WriteLine("The reverse string of '{0}' is: {1}",str,getReverse(str));
    Console.WriteLine("The reverse string of '{0}' is: {1}", str, getReverseUsingBulidingFunction(str));
    Console.ReadLine();
}

Answer 6

public static String reverseString(String str)
{
    StringBuilder sb = new StringBuilder();

    for (int i = str.length() - 1; i >= 0; i--)
    {
        sb.append(str[i]);
    }

    return sb.toString();
}

Answer 7

Использование строки:

String abc = "abcd";
int a= abc.length();

String reverse="";

for (int i=a-1;i>=0 ;i--)
{
    reverse= reverse + abc.charAt(i);
}
System.out.println("Reverse of String abcd using invert array is :"+reverse);

Использование StringBuilder:

    String abc = "abcd";
    int a= abc.length();
    StringBuilder sb1 = new StringBuilder();

    for (int i=a-1;i>=0 ;i--)
    {
        sb1= sb1.append(abc.charAt(i));
    }
    System.out.println("Reverse of String abcd using StringBuilder is :"+sb1);

Answer 8

Использование нескольких потоков для замены элементов:

    final char[] strArray = str.toCharArray();

    IntStream.range(0, str.length() / 2).parallel().forEach(e -> {
        final char tmp = strArray[e];
        strArray[e] = strArray[str.length() - e - 1];
        strArray[str.length() - e - 1] = tmp;
    });
    return new String(strArray);

Answer 9

Одним из вариантов может быть обмен элементов.

int n = length - 1;
char []strArray = str.toCharArray();
for (int j = 0; j < n; j++) {
   char temp = strArray[j];
   char temp2 = strArray[n];
   strArray[j] = temp2;
   strArray[n] = temp;
   n--;
  }

Answer 10

static String ReverseString(String input) {
    var len = input.Length - 1;
    int i = 0;
    char[] revString = new char[len+1];
    while (len >= 0) {
        revString[i] = input[len];
        len--; 
        i++;
    }
    return new string(revString);   
}

Почему мы не можем придерживаться простейшего цикла и почитать с чтением символов и продолжать добавлять в массив символов, я наткнулся на интервью на доске, где интервьюер установил ограничения на неиспользование StringBuilder и встроенных функций.