skip to Main Content

This is driving me insane, because I feel like it shouldn’t be a problem for me, and yet, here I am hoping one of you will take mercy on me. This function takes an array of strings and returns the longest common prefix. It seems to do that fine. The problem is that I want it to return null if there is no common prefix. Instead it returns nothing. With this particular input, it’s comparing the first letter in all words from index 1 onward to the first letter in the word at index 0. It gets to sunflower, sees that f !== s, but instead of returning null, I get nothing at all. What am I missing?

function prefix(words) {
  for (let i = 0; i < words[0].length; i++) {
    const char = words[0][i];
    for (let j = 1; j < words.length; j++) {
      if (i === words[j].length || words[j][i] !== char) {
        return words[0].substring(0, i);
      } 
    }
  }
  // No common prefix found
  return null;
}
console.log(prefix(["flower", "flowers", "floyd", "flow", "sunflower", "floor"]))

4

Answers


  1. Here’s what’s happening

    In the case of ["flower", "flowers", "floyd", "flow", "sunflower", "floor"], the loop iterates through the characters of the first word and compares them to the other words.

    When i reaches the length of the first word (i = 5), there is no exit condition for the outer loop, so it continues to the next iteration.

    However, there’s no corresponding character in the other words, so the inner loop conditions (i === words[j].length || words[j][i] !== char) are not met.

    Since the loop completes without returning anything and all the words are not the same, the function ends without a return statement.

    In JavaScript, when a function doesn’t return anything, it returns undefined, and that’s why you see nothing printed.

    The fix for this is to add a return statement after the outer loop to handle the case where the loop completes without finding a common prefix.

    function prefix(words) {
        /* Check if words list is 0, since prefix will always be null
        in this case */
        if (words.length === 0) return null; 
    
        for (let i = 0; i < words[0].length; i++) {
            const char = words[0][i];
            for (let j = 1; j < words.length; j++) {
                if (i === words[j].length || words[j][i] !== char) {
                    if (i === 0) return null;
                    return words[0].substring(0, i);
                }
            }
        }
    
        return null; // Add this line to handle the missing case
    }
    
    console.log(
        prefix(['flower', 'flowers', 'floyd', 'flow', 'flinging', 'floor'])
    ); // output: null
    
    console.log(
        prefix(['triangle', 'trick', 'trivial', 'triceratops', 'tricycle']) // output: 'tri'
    );
    
    
    Login or Signup to reply.
  2. In your iterations for i=0 and j=4, Your code is comparing ‘s’ and ‘f’ — which will give true for your if condition, but in that case you are returning substring(0,0) for that word which gives an empty string (”) and hence you are returning empty string and not null- so not seeing any thing in your output.
    Hope this helps, any feedback is welcome.

    I solved the problem in a different manner.

    function prefix(words) {
    
    let longestCommonPrefix = ''; //we need to return this prefix and if it is still an empty string we can return null
    //to iterate and access one alphabet at a time
    for(let j=0; j<words[0].length; j++){
        let currChar = words[0][j]; //curr alphabet that needs to be compared if all words have this alphabet in same j'th position, we add it to the prefix string
        // to iterate over different words in the array
        for (let i = 0; i < words.length; i++) {
            // if in any iteration the alphabet doesnt match the currChar, we can return the longestCommonPrefix
            if(words[i][j] !== currChar){
                // ternary operator if longestCommonPrefix has a value of empty string which has a boolean of false, we will return null for that
                return longestCommonPrefix ? longestCommonPrefix : null;
            }
        }
        longestCommonPrefix = longestCommonPrefix + currChar;
    }
    

    // No common prefix found
    return longestCommonPrefix ? longestCommonPrefix : null;
    }
    console.log(prefix(["flower", "flowers", "floyd", "flow", "sunflower", "floor"]))

    Login or Signup to reply.
  3. You could check if the first character is not equal and in this case return null (or undefined):

    function prefix(words) {
      for (let i = 0; i < words[0].length; i++) {
        const char = words[0][i];
        for (let j = 1; j < words.length; j++) {
          // first letter unequal
          if (i === 0 && words[j][i] !== char) {
            return null;
          }
          if (i === words[j].length || words[j][i] !== char) {
            return words[0].substring(0, i);
          } 
        }
      }
      // No common prefix found
      return null;
    }
    
    console.log(prefix(["flower", "flowers", "floyd", "flow", "floor"]))
    console.log(prefix(["flower", "flowers", "floyd", "flow", "sunflower", "floor"]))
    Login or Signup to reply.
  4. You could simplify the code a bit and return null if there’s no more than one iteration to check the prefix:

    function prefix(words) {
        let i = 0;
        while (true) {
            const c = words[0][i];
            for (let j = 1; j < words.length; j++) {
                if (c != words[j][i]) {
                    return i ? words[0].slice(0, i) : null;
                }
            }
            i++; // this will happen when at least 1 character is common
        }
    }
    console.log(prefix(["flower", "flowers", "floyd", "flow", "floor"]))
    console.log(prefix(["flower", "flowers", "floyd", "flow", "sunflower", "floor"]))

    And a benchmark:

    enter image description here

    <script benchmark data-count="10000000">
    
    // @benchmark museum/tom
    {
        function prefix(words) {
          for (let i = 0; i < words[0].length; i++) {
            const char = words[0][i];
            for (let j = 1; j < words.length; j++) {
              // first letter unequal
              if (i === 0 && words[j][i] !== char) {
                return null;
              }
              if (i === words[j].length || words[j][i] !== char) {
                return words[0].substring(0, i);
              } 
            }
          }
          // No common prefix found
          return null;
        }
        prefix(["flower", "flowers", "floyd", "flow", "floor"]);
    }
    
    // @benchmark Alexander
    {
        function prefix(words) {
            let i = 0;
            while (true) {
                const c = words[0][i];
                for (let j = 1; j < words.length; j++) {
                    if (c != words[j][i]) {
                        return i ? words[0].slice(0, i) : null;
                    }
                }
                i++;
            }
        }
        prefix(["flower", "flowers", "floyd", "flow", "floor"]);
    }
    </script>
    <script src="https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js"></script>
    Login or Signup to reply.
Please signup or login to give your own answer.
Back To Top
Search