Reverse the words in string

Question

The task:

Given a string of words delimited by spaces, reverse the words in string. For example, given "hello world here", return "here world hello"

Follow-up: given a mutable string representation, can you perform this operation in-place?

My solution:

const reverseStr = s => s.split(' ').reverse().join(' ');
console.log(reverseStr("hello world here"));

My "in-place" solution:

const reverseStrInPlace = s => {
 let exp = `\\w+$`;
 const startLen = s.lastIndexOf(s.match(/\w+$/)[0]);
 const strLen = s.length;
 const len = (s.match(/\s/g) || []).length;
 for (let i = 0; i < len; i++) {
 exp = `(\\w+)\\s${exp}`;
 s += ` ${s.match(new RegExp(exp), 'g')[1]}`;
 exp = `(\\w+)\\s${exp}`;
 }
 return s.substring(startLen, startLen + strLen);
}
console.log(reverseStrInPlace('hello world here'));

"In-place" algorithms are defined as:

An in-place algorithm transforms the input without using any extra memory. As the algorithm executes, the input is usually overwritten by the output and no additional space is needed for this operation.

Not sure whether this is the right approach for the in-place solution, because, even though I didn't create for the string a new datastructure, i.e. during the operation I overwrite the input and return the overwritten input as the output, but I created other variables, e.g. exp, len, i, etc. i.e. additional space is created for the operation.

• morbusg: Array reverse is mutating, "in-place" method. Strings are immutable.
• Blindman67: In Javascript strings are a basic type and thus can only be copied. You can not modify a string inplace.
• thadeuszlay: Ah, true. In Java as well. How would you have solved it and with what language? @Blindman67
• Blindman67: For performance C or C++, for on the spot solution JavaScript, for when hell freezes over I would create a complicated reverse string class and supporting eco in Java, cut of my ARM, and cry. Sorry I hate Java and would never use it unless there was absolutely no other option (which is never the case)
• thadeuszlay: Why do you hate Java so much? @Blindman67

Answer 1

In javascript, strings are immutable

For character access using bracket notation, attempting to delete or assign a value to these properties will not succeed. The properties involved are neither writable nor configurable. (See Object.defineProperty() for more information.)

So this was either a trick question or the creator was not aware.

The only "mutable string representation" of a javascript string would be an array.

So if the question accepts using an array as the representation of the string, you could do something like this:

function reverse(str){
 const mutable = str.split("");
 
 for(let i = 0; i < mutable.length/2; i++){
 const j = mutable.length-1-i;
 const c = mutable[i];
 mutable[i] = mutable[j];
 mutable[j] = c;
 }
 
 return mutable.join("");
}
const res = reverse("hello world");
console.log(res);

• thadeuszlay: Good idea to loop only to the middle of the array!

Answer 2

Disclaimer: I am not a JavaScripter.

The exp grows inside the loop, and is not bound by a constant; ditto for s. This immediately disqualifies the solution as in-place. Besides, the time complexity (as it matches the growing string in the loop) seems quadratic.

A true in-place algorithm, with linear time complexity, starts with reversing the entire string:

ereh dlrow olleh

Now the words are in the desired order, but are themselves reversed. The only thing left is to reverse individual words.

Implementing a linear time in-place (sub)string reversal is left as an exercise.

• thadeuszlay: Then I guess this is not possible to solve in JS, Because reversing you need either a new array or a new string. (in JS strings are immutable; not sure how you could emulate this in JS and how it would look differently than the first solution in my OP)
• vnp: @thadeuszlay In the wild (say, during an interview) I would accept converting a string to an array first. After all, it is the algorithmic question.