Обратить строку в Java, в O (1)?

Question

Есть ли какие-либо средства в стандартных библиотеках Java, которые, учитывая CharSequence, создают обратное в O (1) раз?

Я предполагаю, что это «легко» реализовать, просто интересно, существует ли оно уже. (Я подозреваю, что причина, по которой это не предлагается, заключается в том, что «простой» способ фактически нарушит кодовые коды с несколькими символами, но во многих случаях мы знаем, что мы не имеем дело с ними).

Благодаря

Update Хех, это немного забавно, что многие думали, это «невозможное», хорошая работа, ребята! Ну, на самом деле это (концептуально) тривиально - pseudojava следует сделать ясно:

class MyReverseString extends String { //of course I can't extend String! 
    final String delegate; 
    MyReverseString(String delegate) { this.delegate = delegate; } 

    int length() { return delegate.length(); } 

    int charAt(int i) { return delegate.charAt(delegate.length() - 1 - i); } 
} 

Я оставляю этот вопрос открытым для некоторых больше, только в редких случаях, когда что-то вроде очевидного решения (например, см Jon Skeet's) уже существует в JDK, и кто-то знает об этом. (Опять же, очень маловероятно из-за этих неприятных кодовых точек).

Редактировать Возможно, путаница исходила от того, что у меня была «строка» в заголовке (но не в String!), Тогда как я только прошу «обратную сторону CharSequence». Если вы были в замешательстве, извините. Я бы надеялся, что O (1) часть будет четко представлять, о чем просят.

И, кстати, this was the question that made me ask this one. (Это случай, когда было бы легче запускать регулярное выражение справа налево, а не слева направо, поэтому может быть какое-то практическое значение даже для реализации простых/сломанных кодовых точек)

Answer 1

Ну, вы можете легко создать реализацию CharSequence, которая возвращает ту же длину, и когда его спросят о конкретном символе, он возвращает значение length-index-1. toString() становится O (п) конечно ...

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

Обратите внимание, что создание инверсное CharSequence (как на теле вашего вопроса) является не то же самое, создавая обратную String (в соответствии с названием вашего вопроса). Фактически, создание String равно O (n) и должно быть.

Пример кода, в основном непроверенными:

public final class ReverseCharSequence implements CharSequence 
{ 
    private final CharSequence original; 

    public ReverseCharSequence(CharSequence original) 
    { 
     this.original = original; 
    } 

    public int length() 
    { 
     return original.length(); 
    } 

    public char charAt(int index) 
    { 
     return original.charAt(original.length() - index - 1); 
    } 

    public CharSequence subSequence(int start, int end) 
    { 
     int originalEnd = original.length() - start; 
     int originalStart = original.length() - end; 
     return new ReverseCharSequence(
      original.subSequence(originalStart, originalEnd)); 
    } 

    public String toString() 
    { 
     return new StringBuilder(this).toString(); 
    } 
} 

Answer 2

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

Answer 3

StringBuffer имеет обратное: http://java.sun.com/j2se/1.4.2/docs/api/java/lang/StringBuffer.html#reverse()

BTW, я предполагаю, вы имели в виду О (п), так как O (1) (как и другие люди упоминали), очевидно, невозможно.

Answer 4

string result = new StringBuffer(yourString).reverse().toString(); 

В зависимости от того, что вы понимаете под O (1) не представляется возможным, так как даже чтение строки сразу необходимо О (п) с п-число символов в строке.

Answer 5

Как все остальные уже писали, это не представляется возможным в O (1) время, так как вы должны выглядеть по крайней мере, каждый персонаж один раз.

Но если вы имели в виду, как это сделать в пространстве O (1), вот оно: если вы хотите сделать это в пространстве O (1), вы, очевидно, не можете выделить новую строку той же длины, но вы должны поменять символы на месте.

Итак, все, что вам нужно сделать, это перебрать слева направо на середину строки и одновременно справа на середину и заменить элементы. Псевдокод (Условные обозначения: Пусть строка s будет доступна на n -м характер через s[n] Если s имеет длину k, мы говорим, что есть элементы 0 к k-1.):

for i=0; i<len(s)/2; ++i{ 
char tmp = s[i] 
s[i] = s[len(s)-1-i] 
s[len(s)-1-i] = tmp 
} 

Итак, вы видите, все, что вам нужно, это вспомогательная переменная tmp, содержащая ваш текущий символ для его замены, поэтому вы можете сделать это в пространстве O (1).

Answer 6

Решение Jon Skeet, скорее всего, наиболее эффективно. Но если вы просто хотите быстро и грязно, это должно сделать это, и я не думаю, что это было бы намного позади в производительности.

StringBuffer reverse=new StringBuffer(original.toString()).reverse(); 

StringBuffer является CharSequence, так что если вы намекаете, что результат должен быть CharSequence это.

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

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

Answer 7

Лучше использовать StringBuilder для обратного просмотра, что является несинхронизированной версией StringBuffer.

Answer 8

for (count = str.length()-1; count >= 0; count--) { 
    tempStr = tempStr.concat(Character.toString(origStr.charAt(count))); 
} 

Answer 9

Здесь у меня есть образец того же метода подстроки и o (n). Я знаю, что использование подстроки будет содержать полную строку памяти.

for(int i = 0; i < s.length(); i++) { 
    s = s.substring(1, s.length() - i) + s.charAt(0) + s.substring(s.length() - i); 
    System.out.println(s); 
} 

Это может вам помочь. Скажи мне, если я ошибаюсь!

Answer 10

// упорно трудились, чтобы понять это

public static String ReverseString(String s){ 
    if (s.length()>0){ 
     s=s.charAt(s.length()-1)+printString(s.substring(0,s.length()-1)); 
    } 
    return s; 
}