力扣

力扣

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
  if (!strs) return ''
  strs = [...new Set(strs)]
  // 根据字符串长度排序,找出最短的字符串进行循环
  const minStr = strs.sort((a, b) => a.length - b.length)[0]
  // 找出所有的组合进行判断
  const arrStr = [...Array(minStr.length)]
    .map((_, index) => minStr.slice(0, index + 1))
    .reverse()
  // console.log(arrStr, 'arrStr')
  // 二分法快速查找
  const arrStrSlice = loopMatch(strs, arrStr)
  // console.log(arrStrSlice, 'arrStr')
  return arrStrSlice.find(v => getAllMatch(strs, v)) || ''
}
var loopMatch = function (strs, arrStr) {
  // 从数组中间开始找,都包含继续加，否则开始减少
  if (arrStr.length <= 3) {
    return arrStr
  }
  // 最有可能匹配的结果
  const stepNum = parseInt(arrStr.length / 2)
  // console.log(stepNum, 'stepNum')
  const currentStr = arrStr[stepNum]
  if (getAllMatch(strs, currentStr)) {
    // 没有匹配到字符串截取数据前面小的字符串
    return loopMatch(strs, arrStr.slice(0, stepNum + 1))
  } else {
    return loopMatch(strs, arrStr.slice(stepNum))
  }
}
/**
 * @param {string[]} strs
 * @param {string} v
 * @return {number}
 */
var getAllMatch = function (strs, v) {
  return !strs.some(str => !new RegExp(`^${v}`).test(str))
}

  var longestCommonPrefix = function (strs) {
    // 根据字符串长度排序,找出最短的字符串进行循环
    const minStr = strs.sort((a, b) => a.length - b.length)[0];
    // 找出所有的组合进行判断
    const arrStr = [...Array(minStr.length)]
      .map((_, index) => minStr.slice(0, index + 1))
      .reverse();
    return arrStr.find((v) => !strs.some((str) => !new RegExp(`^${v}`).test(str))) || '';
  };