Cropping a message using array splits

Question

I am trying to write a simple function to crop a given message to a specific length but at the same time not to cut the words in between and no trailing spaces in the end.

Example:

Input String: The quick brown fox jumped over the fence, K: 11

Output: The quick

Here is what I have tried:

  function crop(message, K) {
  var originalLen = message.length;
  if(originalLen<K)
  {
      return message;
  }
  else
  {
      var words = message.split(' '),substr;

      for(var i=words.length;i > 0;i--)
       {

           words.pop();

            if(words.join(' ').length<=K)
            {
              return words.join(' ');
            }
       }


  }
}

This function works fine but I am not very happy with the implementation. Need suggestions on the performance aspects and will there be a case where this won't work?

Answer 1

This is much slower than necessary. It takes time to construct the array, and more to shorten the array word-by-word. It's easy to imagine how this would go if words contains a whole book and K is some small number.

In general, you want an approach that inspects the original string to decide how much to keep, and then extracts that much, once, before returning it.

A regular expression is an efficient and compact way to find text that meets your criteria. Consider:

function crop(message, K) {
    if(K<1) return "";
    const reK = new RegExp( `^.{0,${K-1}}[^ ](?= |$)` );
    return ( message.match(reK) || [ "" ] )[0];
}

.match returns an array with the matched text as the first element, or null if no match. The alternative [ "" ] will provide an empty string as a return value if there is no match (when the first word is longer than K).

The regular expression, broken down, means:

• ^: match start of string
• .: followed by any character
• {0,10}: ... up to ten times (one less than K)
• [^ ]: followed by a character that is not a space
• (?=…): this is an assertion; it means the following expression must match, but is not included in the result:
  • : followed by a space
  • |: or
  • $: end-of-string

Exercise: can you generalize this approach to recognize any kind of whitespace (tabs, newlines, and so on)?

Answer 2

A fairly simple alternative. Take the maxLength String plus one letter and cut it at the last space. If the maxLength was at the end of a word, the "plus one letter" will take care of that.

The > signs in the tests are there to make any trailing spaces visible.

const crop = (message, maxLength) => {
  const part = message.substring(0, maxLength + 1);
  return part.substring(0, part.lastIndexOf(" ")).trimEnd();
}

console.log(crop("The quick brown fox jumped over the fence", 11)+">");
console.log(crop("The quick brown fox jumped over the fence", 9)+">");
console.log(crop("The quick brown fox jumped over the fence", 8)+">");
console.log(crop("The              ", 6)+">");
console.log(crop("The quick ", 20)+">");

The other answers have very good explanations. I just felt a really simple solution was missing.

Answer 3

Your code looks great.

Oh My Goodness's solution is really great.

---

If you wish, you might be able to design an expression that would do the entire process. I'm not so sure about my expression in this link, but it might give you an idea, how you may do so:

([A-z0-9\s]{1,11})(\s)(.*)

This expression is relaxed from the right and has three capturing groups with just a list of chars that I have just added in the first capturing group and I'm sure you might want to change that list.

You may also want to add or reduce the boundaries.

Graph

This graph shows how the expression would work and you can visualize other expressions in this link:

Performance Test

This JavaScript snippet shows the performance of that expression using a simple 1-million times for loop.

const repeat = 1000000;
const start = Date.now();

for (var i = repeat; i >= 0; i--) {
	const string = 'The quick brown fox jumped over the fence';
	const regex = /([A-z0-9\s]{1,11})(\s)(.*)/gm;
	var match = string.replace(regex, "$1");
}

const end = Date.now() - start;
console.log("YAAAY! \"" + match + "\" is a match 💚💚💚 ");
console.log(end / 1000 + " is the runtime of " + repeat + " times benchmark test. 😳 ");

Testing Code

const regex = /([A-z0-9\s]{1,11})(\s)(.*)/s;
const str = `The quick brown fox jumped over the fence`;
const subst = `$1`;

// The substituted value will be contained in the result variable
const result = str.replace(regex, subst);

console.log('Substitution result: ', result);

Answer 4

A Code Review

Your code is a mess,

• Inconsistent indenting.
• Poor use of space between tokens, and operators.
• Inappropriate use of variable declaration type let, var, const.
• Contains irrelevant / unused code. eg substr

Fails to meet requirements.

You list the requirement

"no trailing spaces in the end."

Yet your code fails to do this in two ways

When string is shorter than required length

 crop("trailing spaces     ", 100); // returns "trailing spaces     "

When string contains 2 or more spaces near required length.

 crop("Trailing spaces   strings with extra spaces", 17); // returns "Trailing spaces  "

Note: There are various white space characters not just the space. There are also special unicode characters the are visually 1 character (depending on device OS) yet take up 2 or more characters. eg "👨‍🚀".length === 5 is true. All JavaScript strings are Unicode.

Rewrite

Using the same logic (build return string from array of split words) the following example attempts to correct the style and adherence to the requirements.

I prefer 4 space indentation (using spaces not tabs as tabs always seem to stuff up when copying between systems) however 2 spaces is acceptable (only by popularity)

I assume that the message was converted from ASCII and spaces are the only white spaces of concern.

function crop(message, maxLength) {       // use meaningful names
    var result = message.trimEnd();       // Use var for function scoped variable
    if (result.length > maxLength) {      // space between if (  > and ) {
        const words = result.split(" ");  // use const for variables that do not change
        do {
            words.pop();
            result = words.join(" ").trimEnd();  // ensure no trailing spaces
            if (result.length <= maxLength) {    // not repeating same join operation
                break;
            }
        } while (words.length);
    }
    return result;
}

Note: Check runtime has String.trimEnd or use a polyfill or transpiler.

Update \$O(1)\$ solution

I forgot to put in a better solution.

Rebuilding the string is slow, or passing the string through a regExp requires iteration over the whole string.

By looking at the character at the desired length you can workout if you need to move down to find the next space and then return the end trimmed sub string result, or just return the end Trimmed sub string.

The result has a complexity of \$O(1)\$ or in terms of \$n = K\$ (maxLength) \$O(n)\$

function crop(message, maxLength) {
    if (maxLength < 1) { return "" }
    if (message.length <= maxLength) { return message.trimEnd() }
    maxLength++;
    while (--maxLength && message[maxLength] !== " ");
    return message.substring(0, maxLength).trimEnd();
}

It is significantly faster than any other solutions in this question.