Inverse une chaîne dans Java, dans O (1)?

Question

Y a-t-il des fonctions dans les bibliothèques Java standard qui, avec une séquence CharSequence, produisent l'inverse en O (1)?

Je suppose que c'est "facile" à implémenter, je me demandais simplement s'il existe déjà. (Je soupçonne que la raison pour laquelle cela n'est pas offert est que la manière "facile" serait en fait de casser les points de code multi-char - mais dans beaucoup de cas, nous savons que nous n'en avons pas).

Merci

Mise à jour Heh, il est un peu amusant que la plupart ont pensé que ce "impossible", bon travail les gars! Eh bien, en fait, il est (conceptuellement) trivial - pseudojava suit pour préciser:

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

Je laisse la question ouverte pour un peu plus, juste les rares cas où quelque chose comme la solution évidente (par exemple, voir Jon Celui de Skeet) existe déjà dans le JDK et quelqu'un le sait. (Encore une fois, hautement improbable en raison de ces points de code méchant).

Modifier Probablement la confusion est venue de moi ayant "chaîne" dans le titre (mais pas String!), Alors que je demande seulement "l'inverse d'une CharSequence". Si vous étiez confus, désolé. J'aurais espéré que la partie O (1) indiquerait clairement ce qui était demandé.

Et en passant, this was the question that made me ask this one. (C'est un cas où il serait plus facile d'exécuter une regex de droite à gauche, pas de gauche à droite, donc il peut y avoir une valeur pratique même pour l'implémentation simple/broken-codepoints)

Answer 1

Eh bien, vous pouvez facilement produire une implémentation de CharSequence qui renvoie la même longueur, et lorsqu'on lui demande un caractère particulier, retourne celle de length-index-1. toString() devient O (n) bien sûr ...

Création qui renversait CharSequence serait O (1) - tout ce qu'il est arrivé à faire est de stocker une référence à la CharSequence d'origine, après tout. Itérer sur tous les personnages de la séquence va évidemment être O (n).

Notez que la création d'un CharSequence inversé (selon le corps de votre question) est pas la même que la création d'un inversé String (selon le titre de votre question). En fait produire la chaîne est O (n), et doit être.

Exemple de code, la plupart du temps non testé:

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

Ceci est impossible. Pour inverser une chaîne, vous devez traiter chaque caractère au moins une fois, par conséquent, il doit être au moins O(n).

Answer 3

StringBuffer a un revers: http://java.sun.com/j2se/1.4.2/docs/api/java/lang/StringBuffer.html#reverse()

BTW, je suppose que vous vouliez dire O (n) parce que O (1) (comme d'autres personnes ont mentionné) est évidemment impossible.

Answer 4

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

Selon ce que vous entendez sous O (1), il ne semble pas possible, car la lecture même la chaîne a besoin d'une fois O (n) n étant le nombre de caractères dans la chaîne.

Answer 5

Comment tous les autres ont écrit déjà, il est impossible dans O (1) le temps, puisque vous ne devez regarder au moins à chaque fois que le caractère. Mais si vous vouliez dire comment le faire dans l'espace O (1), voici: Si vous voulez le faire dans l'espace O (1), vous ne pouvez évidemment pas allouer une nouvelle chaîne de la même longueur, mais vous avoir à échanger les caractères sur place.

Il ne vous reste plus qu'à parcourir de gauche à droite le milieu de la chaîne et simultanément de droite à gauche et à échanger les éléments. (Conventions pseudocode: Laissez chaîne s être accessible au n caractère -ème via s[n] Si s a une longueur k, on dit qu'elle a des éléments 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 
} 

Vous voyez, tout ce que vous avez besoin est un variable auxiliaire tmp contenant votre caractère actuel pour l'échanger, de sorte que vous pouvez le faire dans l'espace O (1).

Answer 6

La solution de Jon Skeet est probablement la plus efficace. Mais si vous voulez juste un rapide et sale, cela devrait le faire et je ne pense pas que ce serait loin derrière dans la performance.

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

Un StringBuffer est un CharSequence, donc si vous voulez dire que le résultat doit être un CharSequence, c'est. Eh bien, cela pourrait être plus rapide que la solution de M. Skeet si vous examinez la séquence plusieurs fois, car cela élimine la surcharge du calcul pour trouver la bonne position de char chaque fois que vous lisez un caractère. Ça va le faire juste une fois par personnage.

Si j'allais en faire un milliard, peut-être que je ferais un benchmark.

Answer 7

Mieux encore utiliser StringBuilder pour inverser, qui est la version non synchronisée de StringBuffer.

Answer 8

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

Answer 9

Ici, j'ai un échantillon de la même en utilisant la méthode de sous-chaîne et o (n). Je suis conscient que l'utilisation de la sous-chaîne tiendra la mémoire de chaîne complète.

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

Ceci pourrait vous aider. Dis-moi si j'ai tort !!

Answer 10

// travaillé dur pour comprendre cela

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