最长公共前缀.md

Longest Common Prefix

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

Input: ["flower","flow","flight"]
Output: "fl"

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

Solution

// Horizontal comparison
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if(strs.length === 0) return "";
    return strs.reduce( (pre, cur) => {
        var tmp = "";
        for(let i=0;i<pre.length; ++i){
            if(pre[i] === undefined || pre[i] !== cur[i]) break;
            else tmp += cur[i];
        }
        return tmp;
    })
};

// Vertical comparison
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    var n = strs.length;
    var target = "";
    var interrupt = false;
    var i = -1;
    while(true) {
        ++i;
        if(!strs[0]) return "";
        var tmp = strs[0][i];
        for(let k=0; k<n; ++k){
            if(strs[k][i] === undefined || tmp !== strs[k][i]) {
                interrupt = true;
                break;
            }
        }
        if(interrupt) break;
        target = `${target}${tmp}`;
    }
    return target;
};

Idea

The horizontal comparison method uses the reduce method of the Js standard library to return the result of each comparison as the first parameter passed to the function for the next comparison, and the second parameter is the current string. Note that the reduce method computes n-1 times for an array of length n when there is no third parameter. The vertical comparison means comparing each character in the string array one by one, constantly looping through each character of the string in the array. During the comparison, the loop ends and returns the result when a different character is encountered in the column.

Daily Question

https://github.com/WindrunnerMax/EveryDay

Reference

https://leetcode-cn.com/problems/longest-common-prefix/