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++) {
const mask = i.toString(2)
...
}
then apply that mask to the input string and place dots where we have 1 in our binary mask
...
const mask = i.toString(2)
let result = ''
for (let j = 0; j < text.length; j++){
result += text[j]
if(j === mask.length) break;
// 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.
A brief google search on adding leading zeros to binary numbers will lead you to
var n = num.toString(2);
n = "00000000".substr(n.length) + n;
or
function pad(n, width, z) {
z = z || '0';
n = n + '';
return n.length >= width ? n : new Array(width - n.length + 1).join(z) + n;
}
or somthing like
function pad(num, size) {
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++) {
const mask = i.toString(2).padStart(text.length - 1, "0");
let result = "";
for (let j = 0; j < text.length; j++) {
result += text[j];
if (j === mask.length) break;
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.
Top comments (0)