14.最长公共前缀.md

题目

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

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

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

示例 2:
输入: ["dog","racecar","car"]
输出: ""

解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。

挨个遍历每个字符串的字母，相同加到result，不同返回result

var longestCommonPrefix = function(strs) {
  let result = ''

  if (strs.length === 0) {
    return result
  }

  for (let i = 0; i < strs[0].length; i++) {
    const flag = strs[0].slice(0, i+1)
    for (let j = 1; j < strs.length; j++) {
      const str = strs[j]
      if (str.indexOf(flag) !== 0) {
        return result
      }
    }
    result = flag
  }

  return result
}

构建trie树，然后通过trie树查找

var longestCommonPrefix = function(strs) {
  //构建trie树
  function Trie (value) {
    this.value = value || ''
    this.isEnd = false
    this.children =  {}
  }

  let root = new Trie()
  let flag = root

  for (let i = 0; i < strs.length; i++) {
    const str = strs[i]
    //排除掉特殊情况
    if (str === '') return ''

    for (let j = 0; j < str.length; j++) {
      const char = str[j]
      if (!flag.children[char]) {
        flag.children[char] = new Trie(char)
      }

      if (j === str.length - 1) {
        flag.children[char].isEnd = true
      }
      flag = flag.children[char]
    }
    flag = root
  }

  //进行查找
  let fake = root
  let result = ''
  while (fake) {
    if (fake.isEnd || Object.keys(fake.children).length !== 1) break

    let key = Object.keys(fake.children)[0]

    result += key
    fake = fake.children[key]
  }

  return result
}