The title

img01

Analysis of the

It’s a simple topic, but it’s actually quite popular in the open source community because a developer was unhappy with NPM and unpublished all of his modules. These include the widely-used Left-pad, which has led to the failure of many tools to build Babel, ReactNative, Ember, and more.

The idea is very simple, directly on the left side of the completion can be:

const leftpad = (str, c, len) = > {
  if(! c && c ! = =0) c = "";
  len = len - str.length;
  return c + Array(len).join(c) + str;
};
Copy the code

The official Babel code is similar to this:

img02

However, this code was ridiculed by the boss left ear mouse, and he also gave his own idea: dichotomy.

The first way to think about it is that the time complexity of the algorithm is On, so if you want to concatenate 20 zeros in front of the string, then you need to concatenate 20 times.

But if we saved the result each time, we would get the following cache:

1 0
2 00
3 0000
4 00000000
Copy the code

In this case, only two strings numbered 4 and one string numbered 3 are needed to fill 20, which is far more efficient than the direct loop and its time complexity is Olog2n.

For using dichotomy to solve this problem, we need to note that:

  • It returns when len is 1left + str
  • When len is an odd numberc + leftThe value of the toleft

💡 in fact, the above conclusion can be drawn by backward deduction. When the length required to complete is 1, it can directly return 0 + STR, then left is 0. When c is equal to 3. We need to return 0 + 00 + STR, where left is 0, c is 00, and so on.

The code is as follows:

const leftpad = (str, c, len) = > {
  len = len - str.length;
  c = String(c);
  let total = "";
  while (len) {
    if (len % 2= = =1) {
      total += c;
    }
    if (len === 1) {
      return total + str;
    }
    c += c;
    len = parseInt(len / 2); }};Copy the code