最长公共前缀

[xszi]

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

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

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""

解释: 输入不存在公共前缀。

leetcode

场景案例【网易】：

有一个场景，在一个输入框输入内容，怎么更加高效的去提示用户你输入的信息，举个例子，你输入天猫，那么对应的提示信息是天猫商城，天猫集团，这个信息如何最快的获取，有没有不需要发请求的方式来实现？

提示：

数据请求：防抖、节流 数据存储处理：Trie树

[xszi]

方法1： 公共指针法

const longestCommonPrefix = (arr) => {
    if (!arr || !arr.length) return '';

    let currentIndex = 0

    while (true) {
        // 取数组第一个元素的第一个字符作为比较的参照
        let refer = arr[0][currentIndex]
        // 是否全部匹配
        const currentAllMatched = arr.reduce((prev, str) => {
            return prev && str.charAt(currentIndex) === refer
        }, true)

        if (currentAllMatched) {
            currentIndex++
        } else {
            break
        }
    }

    return arr[0].substring(0, currentIndex)
}

方法2： 逐个比较

const longestCommonPrefix = (arr) => {
    if (!arr || !arr.length) return ''

    let prev = arr[0]
    for(let i = 1; i < arr.length; i++) {
        let j = 0
        for(; j < prev.length && j < arr[i].length; j++) {
            if (prev.charAt(j) !== arr[i].charAt(j)) break
        }
        prev = prev.substring(0, j)
        if (prev === '') return ''
    }
    return prev
}

方法3：仅需最大、最小字符串的最长公共前缀

解题思路： 获取数组中的最大值及最小值字符串，最小字符串与最大字符串的最长公共前缀也为其他字符串的公共前缀，即为字符串数组的最长公共前缀 例如： abc 、 abcd 、ab 、ac ，最小 ab 与最大 ac 的最长公共前缀一定也是 abc 、 abcd 的公共前缀

const longestCommonPrefix = (arr) => {
    if (!arr || !arr.length) return ''
    if (arr.length === 1) return arr[0]

    let min = 0, max = 0
    for (let i = 0; i < arr.length; i++) {
        if (arr[min] > arr[i]) min = i
        if (arr[max] < arr[i]) max = i
    }

    for (let j = 0; j < arr[min].length; j++) {
        if (arr[min].charAt(j) !== arr[max].charAt(j)) {
            return arr[min].substring(0, j)
        }
    }

    return arr[min]
 }

方法4：分而治之，递归思想

const longestCommonPrefix = (arr) => {
    if (!arr || !arr.length) return ''
    let length = arr.length
    if (length === 1) return arr[0]

    const mid = Math.floor(length / 2),
          left = arr.slice(0, mid),
          right = arr.slice(mid, length)

    return getCommonPrefixOfTwo(longestCommonPrefix(left), longestCommonPrefix(right))

}

const getCommonPrefixOfTwo = (left, right) => {
    let i = 0
    for (; i < left.length && i < right.length; i++) {
        if (left.charAt(i) !== right.charAt(i)) break
    }
    return left.substring(0, i)
}