【LeetCode分享】寻找公共最长前缀

题目14. 寻找公共最长前缀

题目描述

要求： 编写一个函数来查找字符串数组中的最长公共前缀。

            如果不存在公共前缀，返回空字符串 `""`。

示例
输入：strs = ["flower","flow","flight"]
输出："fl"

思路1. 横向搜索

我们可以遍历字符串数组，字符串两两进行比较，找出其中的公共前缀，在比较过程中，公共前缀长度不会增加，只会保持不变或者递减，当变为0时，说明没有公共前缀，此时返回”“。若字符串数组长度为1，则直接返回第一个元素即可。

例如
寻找strs = ['flower','flow','flight','flat']的最长前缀。

1. 比较flower和flow这两个字符串，找出公共前缀flow
2. 将上一次的公共前缀flow与flight进行比较，找出公共前缀fl
3. 将上一次的公共前缀fl与flat进行比较，找出公共前缀fl
4. 遍历结束，返回公共前缀fl

下面是JavaScript实现

/**
 * 思路：
 * 两两比较，找出最长的公共前缀，然后这个公共前缀和下一个词比较
 * 只要公共前缀不为空，且没有到最后一个词，就继续比较，否则停止，并返回前缀
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
    let commonPrefix = ''
    let count = strs.length 
    let prefixPerTime = strs[0]
    for (let i = 1; i < count; i++) {
        let a = prefixPerTime
        let b = strs[i]
        prefixPerTime = findCommonPrefix(a, b)
        if (prefixPerTime.length === 0) {
            return ''
        }
    }
    commonPrefix = prefixPerTime
    return commonPrefix
}

/**
 * 找出公共前缀
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
function findCommonPrefix(a, b) {
    let len = Math.min(a.length, b.length)
    let subStr = a.substring(0, len)
    for (let i = 0; i < len; i++) {
        if (a[i] !== b[i]) {
            return a.substr(0, i)
        }
    }
    return subStr.substring(0, len)
}

思路2 纵向搜索

我们可以将所有字符串纵向排列，从下标0开始遍历每个字符，假设索引为index，当我们发现index为某个值的时候，字符不唯一，则停止遍历，返回公共前缀。

例如
寻找strs = ['flower','flow','flight','flat']的最长前缀。

1. 将所有字符串纵向排列，并用最短的字符串长度为基准，进行截断。
flow
flow
flig
flat
2.从左到右遍历每个字符，找到出现不同字符的那一列的下标index。
3.公共前缀就是下标从0到index-1的子串

下面是JavaScript实现

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
    let count = strs.length
    let commonPrefix = []
    let len = strs[0].length
    for(let i = 0 ; i < len ; i++) {
        let c = strs[0][i]
        for(let k = 1 ; k <count;k++) {
            let c_ = strs[k][i]
            if(c !== c_) {
                return commonPrefix.join('')
            }
        }
        commonPrefix.push(c)
    }
    return commonPrefix.join('')
}

思路3 二分搜索

同纵向搜索，我们首先也是将所有字符串纵向排列，不过在搜索最长公共前缀右边界的时候，可以不用依次遍历的方式，而采用二分搜索的方法。找到一个中心点，左侧如果字符串相同则右边界在右侧，反之在左侧。确定一侧后再次进行二分搜索，不断找下去，即可找到右边界。

例如
寻找strs = ['flower','flow','flight','flat']的最长前缀。

1. 统一字符串长度，即取最小的字符串的长度为统一长度（公共前缀长度必然小等于该值），此处minLen=4

2. 将所有字符串按照统一长度截断后，纵向排列，即

   ['flow','flow','flig','flat']
   

3. 进行二分搜索，确定中心点 ，并确定

4. 验证字符串的子串是否相同，此处都为

5. 取重新回到步骤3（若不相同则取重新回到步骤3）

6. 此时验证子串发现不同，停止。

7. 返回公共前缀，索引为即
   下面是JavaScript实现

/**
 * 采用二分法找到最长公共前缀
 * 1. 首先确定所有字符串的最小长度minLen
 * 2. 在0~minLen区间上二分查找，如果0~mid相同，则前缀在mid右边，反之在左
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
    if (strs == null || strs.length === 0) {
        return ''
    }
    if (strs.length === 1) return strs[0]
    let minLen = strs[0].length
    for (let str of strs) {
        minLen = Math.min(str.length, minLen)
    }
    // 进行二分查找
    let low = 0,
        high = minLen - 1
    while (low <= high) {
        let mid = Math.floor((high - low) / 2) + low
        if (isEqual(strs, low, mid)) {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return strs[0].substring(0, low)
}

/**
 * 判断字符数组中所有字符是否相同
 * @param {string[]} strs
 * @param {number} low
 * @param {number} high
 * @return {boolean}
 */
function isEqual(strs, low, high) {
    let prefix = strs[0].substring(low, high + 1)
    for (let i = 1; i < strs.length; i++) {
        if (prefix !== strs[i].substring(low, high + 1)) {
            return false
        }
    }
    return true
}