14.Longest Common Prefix

Description

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: ["flower","flow","flight"]
Output: "fl"

Example 2:

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

Note:

All given inputs are in lowercase letters a-z.

分析和方案

求一个字符串数组中，共同的最长的开始文字段

思路，先比对头两个字符串中，最长的相同文字头，然后拿来和第三个比较，以此类推

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if(strs == null || strs.length == 0) return "";

    // same表示目前發現的共同字首，一開始為strs[0]
    var same = strs[0];

    // 只需要比對same跟目前字串共同的字元就好
    for(var i = 1 ; i<strs.length ; i++){
        var str = strs[i];

        // 取目前的字串str跟same相等的部分做為新的same
        var j = 0;
        for(; j < same.length ; j++){
           if(same[j] != str.charAt(j)){
                break;
           } 
        }
        // same與目前字串str前幾位相同，就做為新的same
        same = same.slice(0,j);
    }

    return same;
};

或者：

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    var out = ''
    if(strs.length === 0) return out
    if(strs.length === 1) return strs[0]
    var s = strs[0]
    for ( i = 0; i < s.length; i++){
        for ( j = 1; j < strs.length; j++){

            if(strs[j][i] && strs[j-1][i] && strs[j][i] === strs[j-1][i]){
                // console.log('a,',strs[j][i],j,i,out)
                if (j===strs.length-1) out += strs[j][i]
            }else{
                return out
            }
        }
    }
    return out
};

最快

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if (strs === null || strs.length === 0) {
        return "";
    }

    var isCommonPrefix = function(strs, len) {
        var substr = strs[0].substring(0, len);
        for (i = 1; i < strs.length; i++) {
            if (!strs[i].startsWith(substr)) { return false; }
        }
        return true;
    }

    var minLen = Number.MAX_SAFE_INTEGER;
    for (i = 0; i < strs.length; i++) {
        minLen = Math.min(minLen, strs[i].length);
    }
    var low = 1;
    var high = minLen;
    while (low <= high) {
        var middle = Math.floor((low + high) / 2);
        if (isCommonPrefix(strs, middle)) {
            low = (middle + 1);
        }
        else {
            high = (middle - 1);
        }
    }
    return strs[0].substring(0, Math.floor((low+high)/2));
};

第二

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    var index= 0;
    var len = strs.length;
    if(len == 0) {return '';}
    var temp = strs[0].length;
    for(var i = 0; i<strs.length;i++){
        if(strs[i].length < temp){
            temp = strs[i].length;
            index = i;
        }
    }
    var res = '';
    var b = false;
    for(var i = 0;i<strs[index].length; i++){
        for(var j = 0; j<strs.length; j++){
            if(strs[j][i] !== strs[index][i]){
                b = true;
                break;
            }
        }
        if(b){
            break;
        }else{
            res += strs[index][i];    
        }

    }
    return res;
};

第三

/**
 * @param {string[]} strs
 * @return {string}
 */
function findShortestWord(strs) {
    let shortestWordLength = strs[0].length;

    for (let i = 1; i < strs.length; i++) {
        if (shortestWordLength > strs[i].length) {
            shortestWordLength = strs[i].length;
        }
    }
    return shortestWordLength;
}

let longestCommonPrefix = function(strs) {
    if (strs.length == 0) {
        return "";
    } else if (strs.length == 1) {
        return strs[0];
    }

    let shortestWordLength = findShortestWord(strs);
    let longestCommonPre = "";
    let firstWord = strs[0];

    for (let i = 0; i < shortestWordLength; i++) {
        j = 1;
        while (strs.length > j) {
            if (firstWord.charAt(i) !== strs[j].charAt(i)) {
                return longestCommonPre;
            } 
            j++;
        }
        longestCommonPre += firstWord.charAt(i);
    }
    return longestCommonPre;
};