最长公共前缀

前缀递增

最直观的想法

const minStr = (strs: string[]): string => strs.reduce((c ,r) => r.length > c.length ? r : c)

function longestCommonPrefix(strs: string[]): string {  
  const str = minStr(strs)
  let prefix = ''

  for (let i = 1; i <= str.length; i++) {
    const cur = str.slice(0, i)
    if (strs.every(str => str.startsWith(cur))) {
      prefix = cur
    }
  }

  return prefix
}

依次比较

取第一项为默认前缀，前缀依次与其他字符串进行比较。

const reducePrefix = (prefix: string, str: string): string => {
  let min = prefix.length > str.length ? str : prefix

  for (let i = 0; i < min.length; i++) {
    if (prefix[i] !== str[i]) {
      return min.slice(0, i)
    }
  }

  return min
}

function longestCommonPrefix(strs: string[]): string {  
  let prefix = strs[0]

  for (let i = 1; i < strs.length; i++) {
    prefix = reducePrefix(prefix, strs[i])
  }

  return prefix
}

减少比较

实际上仅需要比较字符串最短的那一批就好了，但最短的只有一个时还需要与次短数据比较。

但实际上性能没有什么优化。

const collect = (strs: string[]) => strs.reduce((acc, cur) => {
  if (cur.length === acc.len) {
    acc.least.push(cur)
  }

  if (cur.length < acc.len) {
    acc.len = cur.length
    acc.less = acc.least
    acc.least = [cur]
  }

  return acc
}, {
  len: Infinity,
  least: [] as string[],
  less: [] as string[]
})

const compare = (str1: string, str2: string): string => {
  let min = str1.length > str2.length ? str2 : str1

  for (let i = 0; i < min.length; i++) {
    if (str1[i] !== str2[i]) {
      return min.slice(0, i)
    }
  }

  return min
}

function longestCommonPrefix(strs: string[]): string {  
  if (!strs || strs.length === 0) return ''
  if (strs.length === 1) return strs[0]

  const { least, less } = collect(strs)
  if (least.length === 1) {
    least.push(...less)
  }

  let prefix = strs[0]

  for (let i = 1; i < strs.length; i++) {
    prefix = compare(prefix, strs[i])
  }

  return prefix
}

分治

const compare = (str1: string, str2: string): string => {
  let i = 0
  for (; i < str1.length && i < str2.length; i++) {
    if(str1.charAt(i) !== str2.charAt(i)) {
      break
    }
  }

  return str1.slice(0, i)
}

const lcpRec = (strs: string[]): string => {
  const len = strs.length
  if (len === 1) {
    return strs[0]
  }

  let mid = Math.floor(len / 2),
      left = strs.slice(0, mid),
      right = strs.slice(mid, len)

  return compare(lcpRec(left), lcpRec(right))
}

function longestCommonPrefix(strs: string[]): string {  
  if (strs === null || strs.length === 0) return ''
  
  return lcpRec(strs)
}