DEV Community

Alex Blokh

Posted on • Originally published at outdated.me

Dots, Strings and JavaScript pt. 1

It is a very nifty task to pump up algorithmic thinking and clarity into complexity, execution time and memory usage.

On the input you have a string of symbols, on the output you get an array of all possible strings with dots placed inside the string between characters.

``````> abc
[a.bc ab.c a.b.c]

> abcd
[a.bcd, ab.cd, a.b.cd, abc.d ...]
``````

Newcomers in our team who googled the solution on combinatoric forums usually see a connection with permutations. The task above is about combinations(permutations with repetition) if to be precise. We have exactly two choices '.' and '' to fill slots between characters and we have N-1 slots, where N is number of characters. With a brief calculation you can find out that number of combinations is going to be 2 to the power of N-1.

``````const text = 'abc'
const totalCombinations = Math.pow(2, text.length - 1)
``````

Now we have to decide where to put dots on every iteration. The first thing developers lean to do is to convert an index of a loop to a binary representation and then use it as a mask to apply to an input string

``````for (let i = 0; i < totalCombinations; i++) {
...
}
``````

then apply that mask to the input string and place dots where we have `1` in our binary mask

``````...

let result = ''

for (let j = 0; j < text.length; j++){
result += text[j]

// we've filled all slots at this point
// we can also omit the check above, it'll still work
// yet we prefer clarity over code lines

result += mask[j] === '1' ? '.' : ''
}
``````

the code above is almost correct, you might've noticed that we didn't prepend a leading zeros to our binary mask and instead of having `'00'` `'01'`.. we're going to have `0, 1, 10`. Let's fix that.

``````var n = num.toString(2);
n = "00000000".substr(n.length) + n;

or

z = z || '0';
n = n + '';
return n.length >= width ? n : new Array(width - n.length + 1).join(z) + n;
}

or somthing like

var s = num+"";
while (s.length < size) s = "0" + s;
return s;
}

etc...
``````

Yet we can just use a native `String.prototype.padStart()`

``````const mask = i.toString(2).padStart(text.length - 1, '0')
``````

Let's put everything together

``````const text = "abcde";
const total = Math.pow(2, text.length - 1);

const output = [];
for (let i = 0; i < total; i++) {
let result = "";

for (let j = 0; j < text.length; j++) {
result += text[j];

result += mask[j] === "1" ? "." : "";
}

output.push(result)
}

console.log(output)
``````

And give it a run

``````node test.js
[
'abcde',    'abcd.e',
'abc.de',   'abc.d.e',
'ab.cde',   'ab.cd.e',
'ab.c.de',  'ab.c.d.e',
'a.bcde',   'a.bcd.e',
'a.bc.de',  'a.bc.d.e',
'a.b.cde',  'a.b.cd.e',
'a.b.c.de', 'a.b.c.d.e'
]
``````

Great, everything works as expected. When our developers come to that stage of resolving the problem we give them the improvement task, let's have a look at those in the next post.