Build list of prefixes, including the whole string

Question

There is a string "abcdebfkj", we need to transform this string to the below array:

expected o/p:

["a", "a.b", "a.b.c", "a.b.c.d", "a.b.c.d.e", "a.b.c.d.e.b", "a.b.c.d.e.b.f", "a.b.c.d.e.b.f.k", "a.b.c.d.e.b.f.k.j"]

I am able to do that, but was looking for more promising solution if any. I did that in O(n) time complexity. Please let me know if the below can be improved in any way.

function splitString(str) {
 const result = [];
 for (let i = 0; i < str.length; i++) {
 i === 0 ? result.push(str[i]) : result.push(`${result[i-1]}.${str[i]}`);
 }
 return result;
}
console.log(splitString("abcdebfkj"))

How can I avoid checking the index and make the for loop work?

• vnp: Can't be \$O(n)\$. The result itself is \$O(n^2)\,ドル and you cannot build it faster.

Answer 1

I am able to do that, but was looking for more promising solution if any. I did that in O(n) time complexity.

It's not quite clear what you mean by "more promising". But it should be obvious that it can't be done in better than O(str.length²) steps and space.

How can I avoid checking the index and make the for loop work?

The best way to avoid checking the index and make the for loop work is to not use the index and not use a for loop. There are plenty of very powerful iteration methods on Array.prototype like Array.prototype.map or Array.prototype.join, and most importantly Array.prototype.reduce. In fact, there is a nifty little sketch of a proof on the Wikipedia page for Fold (which is the computer science name for reduce), which shows that reduce can do everything a loop can do. There's also Array.from, which is really powerful.

Now that I have praised all of the powerful methods, I have a confession to make: the problem you have is actually a Prefix sum which can be perfectly solved with the scan function. But ... unfortunately, that specific method is missing from Array.prototype.

If scan did exist, the solution would look something like this [I'll add a simplistic implementation of scan just to make it run]:

Array.prototype.scan = 
 function scan(f, z) {
 return this.reduce(
 (acc, el) => acc.concat([f(acc[acc.length - 1], el)]),
 [z]
 );
 }
function splitString(str) {
 return Array.from(str.substring(1)).
 scan(
 (a, b) => `${a}.${b}`,
 str.charAt(0)
 );
}
console.log(splitString("abcdebfkj"));

[Here you can see it in action in the programming language Scala, which does have scan in its standard library: https://scastie.scala-lang.org/JoergWMittag/lGpk4P66SZOovCV5o6jt1Q/19]

Unfortunately, without scan, we have to do a bit more work.

function splitString(str) {
 return Array.from(
 { length: str.length },
 (_, i) =>
 Array.from(
 str.substring(0, i + 1)
 ).
 join(".")
 );
}
console.log(splitString("abcdebfkj"));

The outer Array.from creates an Array of length str.length, and it uses the return value of the arrow function as each element.

The arrow function gets the current index as its argument, it uses the String.prototype.substring method to grab the first i characters of the string, converts that substring into an array of characters using the above-mentioned very versatile Array.from, and then joins the characters back together with a ".".

We can try and more directly re-implement scan:

function splitString(str) {
 return Array.from(str.substring(1)).
 reduce(
 (acc, c) => acc.concat([`${acc.slice(-1)}.${c}`]),
 [str.charAt(0)]
 );
}
console.log(splitString("abcdebfkj"));

This is essentially an inlined version of the above solution using scan and the simple definition of scan.

So, the main trick is to use the methods that ECMAScript provides us, in particular the ones provided on Array and Array.prototype.

• Apoorva Chikara: Don't you think reduce method is designed to make an array to single value? Just clarifying things. Your code works superb and I really understand every piece of it. Also, we are making two array one is from Array.from and another one for acc which take more memory?
• Jörg W Mittag: "Don't you think reduce method is designed to make an array to single value?" – Yes, that's what reduce does: apply a binary operation between all elements of a collection to reduce the collection to a single value. In my case, the single value just happens to be an array itself. There's nothing in the type signature of reduce that forbids that.

Answer 2

I am not into JavaScript anymore, but:

function splitString(str) {
 const result = [];
 var o = "";
 for (let ch of str) {
 result.push(o + ch);
 o += ch + '.';
 }
 return result;
}
function splitString(str) {
 const result = [];
 var o = "";
 Array.fromString(str).forEach(ch => {
 result.push(o + ch);
 o += ch + '.';
 });
 return result;
}
function splitString(str) {
 const result = [];
 var o = "";
 for (let ch of str) {
 result.push(o + ch);
 o = ch + '.';
 }
 return result;
}

Another variable remains, but the backtick evaluation becomes senceless.

Your requirement is fulfilled by:

function splitString(str) {
 let result = str.split(''); // Array with letters
 //let result = Array.fromString(str); // Array with letters
 for (let i = 1; i < str.length; ++i) {
 result[i] = result[i-1] + '.' + result[i];
 }
 return result;
}

• Apoorva Chikara: If you run this code it doesn't return the expected results, but the last one works well.
• Joop Eggen: You are right, corrected, though I intended to let o contain the pushed value.