DEV Community

Cover image for Reverse a String - Four JavaScript Solutions

Reverse a String - Four JavaScript Solutions

Sarah Chima on July 17, 2019

This article was originally published on my blog The reverse a string problem is a common algorithm problem. In this article, we will consider fou...
Collapse
 
bugmagnet profile image
Bruce Axtens • Edited

Actually, you could take the recursion along a bit further and make it a prototype of String, viz:

String.prototype.flip = function () {
  return (this.length === 1) 
    ? this 
    : this.substr(1).flip() + this.substr(0, 1);
};

var original = "lewd i did live - evil did i dwel";
var reversed = original.flip();
Enter fullscreen mode Exit fullscreen mode

Someone'll beat me to a blog post, likely.

Collapse
 
abraham profile image
Abraham Williams

It's generally recommended that you should not extend native prototypes.

developers.google.com/web/updates/...

Collapse
 
markwaterous profile image
Mark

shakes fist at MooTools

Collapse
 
aminmansuri profile image
hidden_dude • Edited

Wouldn't solution #2 (and maybe some of the others) cause an O(n2 ) problem?

for (let character of str) {
    reverseString = character + reverseString;
}

If str has N elements, and you do character + reverseString each time you get n*(n+1)/2 characters copied (ie. O(n2 )).

Whereas option#1 presumably uses only O(n) functions so it should be much faster as data grows and less stress on the GC.

I think it would be best to compare these with benchmarks (with large examples). Because I've found that the one place where code can get super slow is with successive concatenation in a for loop (as in option#2).

Collapse
 
sarah_chima profile image
Sarah Chima

Thanks for the suggestion and the analysis. In subsequent posts, I try to compare the solutions based on their performance.

Collapse
 
theodesp profile image
Theofanis Despoudis

What about an old classic way:

function reverse(str) {
  let result = str.split('');
  for (let i = 0, j = str.length - 1;i < j; i+=1, j-=1) {
    result[i] = str[j];
    result[j] = str[i];
  }

  return result.join('');
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
sarah_chima profile image
Sarah Chima

This is a good improvement to the solution 2. It reduces the loop time by half. Thanks for sharing.

Collapse
 
quantumsheep profile image
Nathanael Demacon

.split('') can be shortened:

[...string].reverse().join('')
Enter fullscreen mode Exit fullscreen mode
Collapse
 
rhysbrettbowen profile image
Rhys Brett-Bowen

Also good because split will fail badly for some utf8 things like emojis

Collapse
 
bugmagnet profile image
Bruce Axtens • Edited

I'm not sure what you'd call this solution, but it does reverse the string:

var times = function (n, fn /*, args*/) {
  var args = [].slice.call(arguments).slice(1);
  for (var i = 0; i < n; i++) {
    fn.call(this, i, args);
  }
  return args[2];
}

var original = "lewd i did live - evil did i dwel";
var result = "";

var reversed = times(original.length, function (i, args) {
    args[2] = args[1].substr(i, 1) + args[2];
  }, original, result);

That's the first time I've written code that uses .call(). Won't be the last time!

Collapse
 
quickhand profile image
quickhand

Short, sweet:

[...str].map((_,i,arr) => arr[arr.length-1-i])
Collapse
 
bugmagnet profile image
Bruce Axtens

I'd forgotten about that third parameter into map. Short, sweet, superb!

Collapse
 
bugmagnet profile image
Bruce Axtens

So after doing .call(), let's do .apply(), viz

Array.prototype.flip = function () {
    for (var i = 0; i < this.length / 2; i++) {
        var tmp = this[this.length - i - 1];
        this[this.length - i - 1] = this[i];
        this[i] = tmp;
    }
    return this;
}

var original = "lewd i did live - evil did i dwel";

var reversed = [].flip.apply(original.split("")).join("");

Okay, maybe it's time to do some real work now.

Collapse
 
bugmagnet profile image
Bruce Axtens

Going nuts here. More ideas, and for something as mundane as a reverse function. Monomania?

function flip3(string) {
  var result = Array(string.length);
  for (var i = string.length - 1, j = 0; i >= 0; i--, j++) {
    result[j] = string.charAt(i);
  }
  return result.join("");
}

function flip4(string) {
    var result = Array(string.length).fill(1);
    result.map(function (item,index) {
        var rhs = string.length - 1 - index;
        result[index] = string.charAt(index);
    });
    return result.join("");
}

Your mileage may vary on flip4's .fill() call. I'm having to use polyfills (long story) and if I don't fill the Array, .map() assumes that there's nothing there to work on.

I do have a couple of ideas yet to exorcise.

Collapse
 
bugmagnet profile image
Bruce Axtens • Edited

This recursion thing is pretty cool. Here's another approach both as a String.prototype and as a standalone function:

String.prototype.flip2 = function() {
  if (1 >= this.length) return this;
  return (
    this.substr(-1) +
    this.substr(1, this.length - 2).flip2() +
    this.substr(0, 1)
  );
};

function flip2(string) {
  if (1 >= string.length) return string;
  return (
    string.substr(-1) +
    flip2(string.substr(1, string.length - 2)) +
    string.substr(0, 1)
  );
}

var x = "lewd i did live - evil did i dwel".flip2();
var y = flip2("lewd i did live - evil did i dwel");

The approach is to take the first character and put it last, take the last character and put it first, and do that to the stuff in the middle.

It's been through the Closure Compiler, thus the 1 >= this.length.

Collapse
 
nsriram profile image
Sriram Narasimhan

Another solution using for loop, but only iterates half the time.

function reverse(str){
  let reversedStr = str
  const length = reversedStr.length
  for(i=0; i< length/2; i++){
    const endIndex = length - (i+1)
    if(endIndex > i){
      const pre = reversedStr.substring(0, i)
      const beginChar = reversedStr.substring(i, i+1)
      const unsorted = reversedStr.substring(i+1,endIndex)
      const endChar = reversedStr.charAt(endIndex)
      const post = reversedStr.substring(endIndex+1)

      //An overkill of swap !
      reversedStr = pre+endChar+unsorted+beginChar+post         
    }
  }
  return reversedStr
}

console.log(reverse("1234567"))
console.log(reverse("123456"))
console.log(reverse("abracadabra"))
console.log(reverse("esrever"))
Collapse
 
fullzero5 profile image
FullZero
Collapse
 
dmikester1 profile image
Mike Dodge

What is this crazy black magic I'm looking at?

Collapse
 
sir_wernich profile image
Wernich ️

first thing i thought of was reduceRight (works in the opposite direction to reduce), with no split or join :)

Array.from(str).reduceRight((acc, ch) => acc.concat(ch));
Collapse
 
mgranados profile image
Martín Granados García

Nice idea for blog posts! It is helpful for people wanting to learn and helpful for you to practice the algos! 💯

Collapse
 
sarah_chima profile image
Sarah Chima

Thank you, Martin.

Collapse
 
leobm profile image
Felix Wittmann • Edited

certainly not very fast, but I'd like destructuring assignment and recursion :)

let reverse = ([h,...r]) => r.length>0 && reverse(r)+h || h;
Collapse
 
javver profile image
Javier Cardona • Edited

Just don't use any emoji with skin color modifier though...

"🤷🏻‍♂️" split on '' becomes 7 "strings"

"🤷🏻‍♂️".split('').reverse().map(c => c.charCodeAt(0).toString(16))
// ["fe0f", "2642", "200d", "dffb", "d83c", "dd37", "d83e"]

That reversed looks... weird.
"️♂‍�🄷�"

Collapse
 
gregbacchus profile image
Greg Bacchus

Would be great to see a performance comparison between then all.

Collapse
 
sarah_chima profile image
Sarah Chima

Yes, I'll consider adding that in subsequent posts. Thanks for the suggestion.

Collapse
 
vyasriday profile image
Hridayesh Sharma

You can find code snippets here. I did the same a couple of days ago
github.com/vyasriday/js-snippets/b...