Topic describes

Write a function to find the longest public prefix in an array of strings. Returns the empty string "" if no public prefix exists. Example 1: Input: STRS = ["flower","flow","flight"] Output: "FL" Example 2: Input: STRS = ["dog","racecar","car"] Output: "" Description: The input does not have a public prefix. Tip: 0 <= strs.length <= 200 0 <= STRS [I]. Length <= 200 STRS [I] consists of lowercase letters onlyCopy the code

Their thinking

Idea 1: Horizontal scan

  • Special treatment:
    • If the length of the STRS string array is empty, return it;
  • Compare the first element in the array as the longest public prefix;
  • Iterate over each element in the array in turn;
    • If the public prefix does not compare with the current comparison element, the current comparison is terminated immediately, break;
    • Update public prefix prefix=prefix.slice(0,j);
    • If the prefix after the update is empty, the subsequent element comparison ends early.

Space-time complexity

  • Time complexity: O(mn)O(mn), where mm is the average length of strings in the string array and nn is the number of strings. In the worst case, each character of each string in the string array is compared once.

  • Space complexity: O(1)O(1). The extra space complexity used is constant.

code

/ * * *@param {string[]} strs
 * @return {string}* /
var longestCommonPrefix = function(strs) {
 // 1. If the array is empty, return it directly
  if(strs.length<=0) {return ' '
  }
  // 2. Compare the first element of the array as the longest public prefix;
  let prefix=strs[0];
  // 3. Compare the public prefix with the remaining elements and update prefix;
  for(let i=1; i<strs.length; i++){let j=0;
      for(; j<prefix.length&&j<strs[i].length; j++){// If the current element comparison is different, exit the comparison round
          if(prefix[j]! ==strs[i][j]){break; }}// Reassign prefix
      prefix=prefix.slice(0,j);
      // If it is already empty, the traversal is terminated early;
      if(prefix===' ') {return ' '}}// end of for 
  return prefix
};
Copy the code

Idea 2: Divide-and-conquer

Space-time complexity

  • Time complexity: O(mn) m represents the average length of all strings in the string array, and n represents the size of the string array
  • Spatial complexity: O(mlogn) Spatial complexity is mainly determined by the number of recursive call layers, the maximum number of layers is logn, each layer needs m space to store the return result.
/ * * *@param {string[]} strs
 * @return {string}* /
var longestCommonPrefix = function(strs) {
  // Divide and conquer
  const lcp=(left,right) = >{
      // The left subscript is equal to the right subscript. Returns the current element directly as the longest public prefix
      if(left===right){
          return strs[left]
      }
      let mid=left+((right-left)>>1);
      let leftLCP=lcp(left,mid);
      let righLCP=lcp(mid+1,right);
       // Finally returns the longest public prefix of two strings
       return longestCommonPrefixHelp(leftLCP,righLCP)
  }
  return lcp(0,strs.length-1)};var longestCommonPrefixHelp=function(leftLCP,righLCP){
    // Compare the longest public prefix between two strings;
    let minlen=Math.min(leftLCP.length,righLCP.length);
    let index=0;
    while(index<minlen&&leftLCP[index]===righLCP[index]){
        index++
    }
    return leftLCP.slice(0,index)
}
Copy the code