leetcode longest common prefix

leetcode longest common prefix

This article consists of a variety of solutions for the leetcode longest common prefix.

Leetcode longest prefix common prefix question

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Solution

The first step is to make sure you understand the question and review examples. Even if it takes you reading the question over and over to understand the requirement, do it.

Solution

We are given an array of strings and we are looking for the longest prefix. Meaning we have to compare each prefix of each given string in the array.

While doin the comparison, if the prefix is the same, we should record it somewhere and that should be answer to the given problem.

  1. Define a function that take an array of string as a parameter. create a variable prefix to hold final resut.

var longestCommonPrefix = function(strs) {
 let prefix = "";
    return prefix; 
};

2. do some checks if the array of strings is null or just one item or the first item is an empty string, if true return empty string as required since there is no common prefix.

var longestCommonPrefix = function(strs) {
 let prefix = "";

   if(strs === null ||  strs.length === 0 || strs[0] === "") return prefix;
    return prefix; 
};

3. Another check if we have only one word in the array of string , we should return the first character as the common prefix.

var longestCommonPrefix = function(strs) {
 let prefix = "";

   if(strs === null ||  strs.length === 0 || strs[0] === "") return prefix;

 if(strs.length === 1) return strs[0];

    return prefix; 
};

3. We will loop each through each each word and compares the prefix. If the same prefix is found add it up to declared prefix.

var longestCommonPrefix = function(strs) {
 let prefix = "";

   if(strs === null ||  strs.length === 0 || strs[0] === "") return prefix;

 if(strs.length === 1) return strs[0];

    return prefix; 
};

var longestCommonPrefix = function(strs) {
 let prefix = "";

   if(strs === null ||  strs.length === 0 || strs[0] === "") return prefix;

 if(strs.length === 1) return strs[0];

    for(i = 0; i < strs[0].length; i++){
        console.log('obs',strs[0][i]);
        const char = strs[0][i];

        for (let j = 1; j < strs.length; j++) {
            console.log('see: ',strs[j][i])
          if(strs[j][i] !== char) return prefix;
            
        }
        prefix = prefix +  char;
    }

    return prefix; 
};

Next, we will run our code

var longestCommonPrefix = function(strs) {
 let prefix = "";

    if(strs === null ||  strs.length === 0 || strs[0] === "") return prefix;

    if(strs.length === 1) return strs[0];
    

    for(i = 0; i < strs[0].length; i++){
        console.log('obs',strs[0][i]);
        const char = strs[0][i];

        for (let j = 1; j < strs.length; j++) {
            console.log('see: ',strs[j][i])
          if(strs[j][i] !== char) return prefix;
            
        }
        prefix = prefix +  char;
    }

    return prefix;
    
};


strs = ["flower","flow","flight"]

console.log(longestCommonPrefix(strs))   // fl

If you still find it difficult to understand, run the following in debug mode.

var longestCommonPrefix = function(strs) {
 let prefix = "";

    if(strs === null ||  strs.length === 0 || strs[0] === "") return prefix;

    if(strs.length === 1) return strs[0];
    

    for(i = 0; i < strs[0].length; i++){
        console.log('obs',strs[0][i]);
        const char = strs[0][i];

        for (let j = 1; j < strs.length; j++) {
            console.log('see: ',strs[j][i])
          if(strs[j][i] !== char) return prefix;
            
        }
        prefix = prefix +  char;
    }

    return prefix;
    
};


strs = strs = ["dog","racecar","car"]

console.log(longestCommonPrefix(strs))

Solution 2

var longestCommonPrefix = function (strs) {
  if (strs.length > 0) {
    let minLen = Math.min(...strs.map(s => s.length))
    const anyStr = strs[0]
    while (minLen) {
      const prefix = anyStr.slice(0, minLen--)
      if (strs.every(s => s.startsWith(prefix))) {
        return prefix
      }
    }
  }
  return ''
};

Solution 3

var longestCommonPrefix = function (strs) {
  let prefix = ''
  if (strs.length > 0) {
    for (let i = 0; ; i++) {
      const c = strs[0][i]
      if (!c) { return prefix }
      for (let j = 0; j < strs.length; j++) {
        if (strs[j][i] !== c) {
          return prefix
        }
      }
      prefix += c
    }
  }
  return prefix
};

If you find this helpful, share.

One thought on “leetcode longest common prefix

Leave a Reply

Your email address will not be published. Required fields are marked *