JavaScript查找最长的公共前缀

给定一个字符串数组，我们必须找到它们之间最长的公共前缀。如果没有前缀，则返回空字符串。

例

输入: ["flower","flow","flight"]
得到的目标值: "fl"

输入: ["dog","racecar","car"]
得到的目标值: ""
There is no common prefix among the input strings.

方法 1：使用排序查找最长的常用前缀。

这个想法是去的。

• 根据字符串的长度按升序对字符串进行排序。
• 然后使用其中最小的，并迭代其中的每个字符，因为max前缀将小于或等于最小的字符串。
• 在每次迭代中，检查其余单词的前缀是否存在，如果存在，则存储它，否则中断并返回字符串。

const longestCommonPrefix = (strs) => {
    //If empty array return empty string
    if(strs.length === 0){
        return "";
    }
    
    //To track the prefix
    let lc = "";
    
    //Sort the string in ascending order
    strs.sort((a, b) => ('' + a).localeCompare(b));
    
    //Get the smallest string.
    let smallest = strs[0];
   
    //so that we have to iterate for it only.
    for(let i = 0; i < smallest.length; i++){
          //Get the first letter
          let current = smallest[i];
         
          //Flag to check if prefix is present in the remaining string
          let isPresent = true;
          
         for(let values of strs){
            //Break if different letter
            if(values[i] !== current){
               isPresent = false;
               break;
            }
         }
         
         //Break the loop if no prefix
         if(i === 0 && !isPresent){
             break;
         }
         
         //Add the prefix
         lc += isPresent ? current : ''; 
    }
    
   //return the prefix
   return lc;
};
 
console.log(longestCommonPrefix(["flower","flow","flight"]));// 结果"f1"
 
 

时间复杂度：O（nlogn +（n *字符串中最小单词的长度））。
空间复杂度：O（1）或O（n），如果我们使用不同的排序。

方法 2：通过从末尾删除字符。

从概念上讲，这就是它的工作原理。

• 从数组中获取第一个单词。
• 迭代数组中的每个单词，并检查它是否不是同一个单词。
• 然后继续从末尾删除字符，直到找到前缀。
• 如果没有前缀并且字符串变为空，则中断并返回空字符串。

const longestCommonPrefix = (strs) => {
    //If empty array
    if(strs.length == 0) {
        return "";
    }
    
    //Get the first word
    let str = strs[0];
    
    //look for prefix in each word
    for (const word of strs) {
        while (word.indexOf(str) !== 0) {
            // remove one character from the end
            str = str.substring(0, str.length - 1);
            if (str === ""){
                break;
            }
        }
    }
    return str;
};

时间复杂度：O（n * 最大字符串的长度）。
空间复杂度：O（1）。