Nuggets team number online, help you Offer rimmon! Click to see details

I. Topic Description:

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

Returns an empty string “” if no common prefix exists.

 

Example 1: Input: STRS = ["flower","flow","flight"] Output: "fl" Example 2: Input: STRS = ["dogcar","racecar","car"] Output: "" Explanation: The input does not have a common prefix. 0 <= STRS. Length <= 200 0 <= STRS [I]. Length <= 200 STRS [ICopy the code

 

Ii. Thinking analysis:

  • Select a string as the standard, and check its prefix string against all the other strings to see if it is the prefix substring of all of them

Three, AC code

/** * @param {string[]} strs * @return {string} */ var longestCommonPrefix = function(strs) { if(strs.length == 0){ return ""; } let str = strs[0]; for(let i = 1; i < strs.length; i++){ while(strs[i].indexOf(str) ! = 0){ str=str.substr(0, str.length - 1); } } return str; }; Status: Elapsed time: 80 ms Memory consumption: 38.7 MBCopy the code

Four,

  • Of course, there is more than one way to do it, and there are many ways to implement it, such as:
  • Method 1: transverse scanning
  • Method two: longitudinal scanning
  • Method three: divide and conquer
  • Method four: binary search

There are other solutions, of course

If all comparisons pass, add the current character to the re. If all comparisons pass, return the re. var longestCommonPrefix = function(strs) { var re = ''; if (! strs.length) return re; for (var j=0; j<strs[0].length; // for (var I =1; i<strs.length; If (STRS [I][j]! =strs[0][j]) return re } re += strs[0][j]; } return re; }; Other solution 2: recursive version of solution 1, some judgment statements need to be added. var longestCommonPrefix = function (strs,re = '') { if (! strs.length) return re; if (strs.length == 1) return strs[0]; for (var i = 1; i < strs.length; i++) { if (! strs[i][0]) return re if (strs[i][0] ! = strs[0][0]) return re strs[i] = strs[i].slice(1,strs[i].length); } re += strs[0][0]; strs[0] = strs[0].slice(1,strs[0].length); return longestCommonPrefix(strs, re); }; The re is initialized to the first element in the array and is compared one by one. If the comparison passes, the re is returned. Otherwise, the last bit is cut until the comparison passes. The comparison here uses regular expressions. var longestCommonPrefix = function(strs) { var re = strs[0] ? strs[0]:''; for (var i=1; i<strs.length; i++){ var regex = new RegExp('^'+re); while (! regex.test(strs[i])&&re.length){ re = re.slice(0,re.length-1); regex = new RegExp('^'+re); } } return re; };Copy the code

For reference only

Refer to the topic

  • Force button (LeetCode)