Comment inverser une chaîne de caractères en place en JavaScript ?

Question

Comment inverser une chaîne en place (ou in-place) en JavaScript lorsqu'elle est passée à une fonction avec une instruction de retour ? Tout cela sans utiliser les fonctions intégrées ? .reverse(), .charAt(), etc.

Merci !

Answer 1

function reverse(s){
    return s.split("").reverse().join("");
}

Mises en garde : http://stackoverflow.com/a/16776621/1636522 .

Answer 2

La technique suivante (ou une technique similaire) est couramment utilisée pour inverser une chaîne de caractères en JavaScript :

// Don’t use this!
var naiveReverse = function(string) {
    return string.split('').reverse().join('');
}

En fait, toutes les réponses postées jusqu'à présent sont une variation de ce modèle. Cependant, cette solution pose quelques problèmes. Par exemple :

naiveReverse('foo

Answer 3

String.prototype.reverse=function(){return this.split("").reverse().join("");}

ou

String.prototype.reverse = function() {
    var s = "";
    var i = this.length;
    while (i>0) {
        s += this.substring(i-1,i);
        i--;
    }
    return s;
}

Answer 4

La question "inverser une chaîne de caractères en place" est une question d'entretien archaïque que les programmeurs C, et les personnes qui ont été interviewées par eux (pour se venger, peut-être ?), posent. Malheureusement, c'est la partie "en place" qui ne fonctionne plus, car les chaînes de caractères dans presque tous les langages gérés (JS, C#, etc.) utilisent des chaînes immuables, ce qui va à l'encontre de l'idée de déplacer une chaîne sans allouer de nouvelle mémoire.

Si les solutions ci-dessus permettent effectivement d'inverser une chaîne de caractères, elles ne le font pas sans allouer plus de mémoire, et ne remplissent donc pas les conditions. Vous devez avoir un accès direct à la chaîne telle qu'elle a été allouée, et être capable de manipuler son emplacement mémoire d'origine pour pouvoir l'inverser sur place.

Personnellement, je déteste vraiment ce genre de questions d'entretien, mais malheureusement, je suis sûr que nous continuerons à les voir dans les années à venir.

Answer 5

On dirait que j'ai 3 ans de retard sur la fête...

Malheureusement, vous ne pouvez pas, comme cela a été souligné. Voir Les chaînes JavaScript sont-elles immuables ? Ai-je besoin d'un "string builder" en JavaScript ?

La meilleure solution suivante consiste à créer une "vue" ou un "wrapper", qui prend une chaîne de caractères et réimplémente les parties de l'API des chaînes de caractères que vous utilisez, en faisant comme si la chaîne était inversée. Par exemple :

var identity = function(x){return x};

function LazyString(s) {
    this.original = s;

    this.length = s.length;
    this.start = 0; this.stop = this.length; this.dir = 1; // "virtual" slicing
    // (dir=-1 if reversed)

    this._caseTransform = identity;
}

// syntactic sugar to create new object:
function S(s) {
    return new LazyString(s);
}

//We now implement a `"...".reversed` which toggles a flag which will change our math:

(function(){ // begin anonymous scope
    var x = LazyString.prototype;

    // Addition to the String API
    x.reversed = function() {
        var s = new LazyString(this.original);

        s.start = this.stop - this.dir;
        s.stop = this.start - this.dir;
        s.dir = -1*this.dir;
        s.length = this.length;

        s._caseTransform = this._caseTransform;
        return s;
    }

//We also override string coercion for some extra versatility (not really necessary):

    // OVERRIDE STRING COERCION
    //   - for string concatenation e.g. "abc"+reversed("abc")
    x.toString = function() {
        if (typeof this._realized == 'undefined') {  // cached, to avoid recalculation
            this._realized = this.dir==1 ?
                this.original.slice(this.start,this.stop) : 
                this.original.slice(this.stop+1,this.start+1).split("").reverse().join("");

            this._realized = this._caseTransform.call(this._realized, this._realized);
        }
        return this._realized;
    }

//Now we reimplement the String API by doing some math:

    // String API:

    // Do some math to figure out which character we really want

    x.charAt = function(i) {
        return this.slice(i, i+1).toString();
    }
    x.charCodeAt = function(i) {
        return this.slice(i, i+1).toString().charCodeAt(0);
    }

// Slicing functions:

    x.slice = function(start,stop) {
        // lazy chaining version of https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/Array/slice

        if (stop===undefined)
            stop = this.length;

        var relativeStart = start<0 ? this.length+start : start;
        var relativeStop = stop<0 ? this.length+stop : stop;

        if (relativeStart >= this.length)
            relativeStart = this.length;
        if (relativeStart < 0)
            relativeStart = 0;

        if (relativeStop > this.length)
            relativeStop = this.length;
        if (relativeStop < 0)
            relativeStop = 0;

        if (relativeStop < relativeStart)
            relativeStop = relativeStart;

        var s = new LazyString(this.original);
        s.length = relativeStop - relativeStart;
        s.start = this.start + this.dir*relativeStart;
        s.stop = s.start + this.dir*s.length;
        s.dir = this.dir;

        //console.log([this.start,this.stop,this.dir,this.length], [s.start,s.stop,s.dir,s.length])

        s._caseTransform = this._caseTransform;
        return s;
    }
    x.substring = function() {
        // ...
    }
    x.substr = function() {
        // ...
    }

//Miscellaneous functions:

    // Iterative search

    x.indexOf = function(value) {
        for(var i=0; i<this.length; i++)
            if (value==this.charAt(i))
                return i;
        return -1;
    }
    x.lastIndexOf = function() {
        for(var i=this.length-1; i>=0; i--)
            if (value==this.charAt(i))
                return i;
        return -1;
    }

    // The following functions are too complicated to reimplement easily.
    // Instead just realize the slice and do it the usual non-in-place way.

    x.match = function() {
        var s = this.toString();
        return s.apply(s, arguments);
    }
    x.replace = function() {
        var s = this.toString();
        return s.apply(s, arguments);
    }
    x.search = function() {
        var s = this.toString();
        return s.apply(s, arguments);
    }
    x.split = function() {
        var s = this.toString();
        return s.apply(s, arguments);
    }

// Case transforms:

    x.toLowerCase = function() {
        var s = new LazyString(this.original);
        s._caseTransform = ''.toLowerCase;

        s.start=this.start; s.stop=this.stop; s.dir=this.dir; s.length=this.length;

        return s;
    }
    x.toUpperCase = function() {
        var s = new LazyString(this.original);
        s._caseTransform = ''.toUpperCase;

        s.start=this.start; s.stop=this.stop; s.dir=this.dir; s.length=this.length;

        return s;
    }

})() // end anonymous scope

Démonstration :

> r = S('abcABC')
LazyString
  original: "abcABC"
  __proto__: LazyString

> r.charAt(1);       // doesn't reverse string!!! (good if very long)
"B"

> r.toLowerCase()    // must reverse string, so does so
"cbacba"

> r.toUpperCase()    // string already reversed: no extra work
"CBACBA"

> r + '-demo-' + r   // natural coercion, string already reversed: no extra work
"CBAcba-demo-CBAcba"

Le truc -- ce qui suit est fait en place par pure mathématique, en visitant chaque caractère une seule fois, et seulement si nécessaire :

> 'demo: ' + S('0123456789abcdef').slice(3).reversed().slice(1,-1).toUpperCase()
"demo: EDCBA987654"

> S('0123456789ABCDEF').slice(3).reversed().slice(1,-1).toLowerCase().charAt(3)
"b"

Cela permet de réaliser des économies importantes si on l'applique à une très grande chaîne, si l'on n'en prend qu'une tranche relativement petite.

Le fait que cela en vaille la peine (par rapport à l'inversion comme une copie comme dans la plupart des langages de programmation) dépend fortement de votre cas d'utilisation et de l'efficacité avec laquelle vous réimplémentez l'API des chaînes de caractères. Par exemple, si tout ce que vous voulez, c'est faire de la manipulation d'index de chaînes de caractères, ou prendre de petits fichiers de type slice ou substr ce qui vous fera gagner de l'espace et du temps. Toutefois, si vous prévoyez d'imprimer de grandes tranches inversées ou des substrats, l'économie réalisée peut être minime, voire pire que de faire une copie complète. Votre chaîne "inversée" n'aura pas non plus le type string mais il est possible d'y parvenir grâce au prototypage.

L'implémentation de la démo ci-dessus crée un nouvel objet de type ReversedString. Elle est prototypée, et donc assez efficace, avec un travail presque minimal et un encombrement minimal (les définitions des prototypes sont partagées). Il s'agit d'une implémentation paresseuse impliquant un découpage différé. Chaque fois que vous exécutez une fonction comme .slice ou .reversed il effectuera des calculs d'indexation. Enfin, lorsque vous extrayez des données (en appelant implicitement .toString() ou .charCodeAt(...) ou autre), il les appliquera de manière "intelligente", en touchant le moins de données possible.

Remarque : l'API de chaîne ci-dessus est un exemple et peut ne pas être parfaitement implémentée. Vous pouvez également utiliser seulement 1 ou 2 fonctions dont vous avez besoin.