This is the 8th day of my participation in the August More text Challenge. For details, see: August More Text Challenge

preface

Js algorithm has been updated for several days, many are related to string, which makes me more aware of how important the processing of string is in JS, today is still a string related problem, the longest public prefix. So here’s how I did it

Topic describes

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 = [“dog”,”racecar”,”car”]

Output: “”

Explanation: Input does not have a common prefix.

Tip:

1 <= strs.length <= 200

0 <= strs[i].length <= 200

STRS [I] consists of lowercase letters only

Their thinking

  • So this algorithm, at first glance, it looks so short, it looks so simple, at least that’s what THEY think, but it’s not
  • Is first of all, I want to divide the input array of multiple strings into a single string array, and then from the table below zero, carries on the comparison to each string array are equal, know is not equal to the position, but there is a problem, we must first clear an input several strings, namely several array, or what we need to do a few times each cycle comparison, second, We have to figure out exactly how many cycles we’re going to do
  • In the first step of converting an array of strings into an array of single strings we can get how many arrays there are, and we can get the length of each array, and we can easily know that the maximum number of loops is the smallest of all the array lengths
  • Now that we know how many times we’re going to loop, what we’re going to do is figure out how many times we’re going to compare each loop, and we’re going to figure out how many values we’re going to compare each loop with strs.length
  • One more thing, we need to find out what the shortest array of strings is, which is the array with the subscript resultIndex
  • So we close the loop and we get what we want, so let’s go to the code above
/ * * *@param {string[]} strs
 * @return {string}* /
var longestCommonPrefix = function(strs) {
     debugger
    var arrLength=[]
    var result=[]
    var arr=[]
    strs.forEach((item,index) = > {
        arr[index]=item
        arrLength.push(arr[index].length)
    })
    var arrlenthValue=arrLength.sort()
    var resultIndex =arrLength.indexOf(arrlenthValue[0])
    var minLength = arrlenthValue[0]
    var strsLength=strs.length
    var nowIndex=0
    while(nowIndex<minLength){
       for(let i=0; i<strsLength-1; i++){if(arr[i][nowIndex]===arr[i+1][nowIndex]){
               continue
           }else{
               return result.join(' ')
           }
       }
        result.push(arr[resultIndex][nowIndex])
        nowIndex++
       
    }
    return result.join(' ')};Copy the code

The running result of LeetCode is as follows:

conclusion

This problem I do very big head, do always confused in the end each loop in the end to compare how many characters in the array, feel that their writing is very complex, there is a better solution to welcome comments, grateful.