最长公共前缀

LeetCode-14

/** 方案一
 * 时间复杂度：O(mn)，其中，m 表示数组中字符串的平均长度，n 表示字符串数组的长度。
 *
 * 虽然节省了代码量，但由于涉及到排序，所以时间复杂度较高，并且需要额外的时间和空间，
 * 因此，在实际应用中，建议根据具体情况选择合适的方法。
 */

var longestCommonPrefix = function (strs = []) {
  if (!strs.length) return ''
  strs.sort() // 排序后字母会根据ASCII码(a-z)进行升序排序
  console.log(strs)
  // 取出第一个和最后一个字符串(排序后的字符串相同前缀的会在前面)
  let firstStr = strs[0]
  let lastStr = strs[strs.length - 1] // strs.pop()
  let i = 0
  while (i < firstStr.length && i < lastStr.length && firstStr[i] === lastStr[i]) {
    i++
  }
  return firstStr.slice(0, i)
}

longestCommonPrefix(['asdf', 'asdg', 'asdqz'])

/** 方案二
 * 时间复杂度：O(mn) 其中，m 表示数组中字符串的平均长度，n 表示字符串数组的长度。
 */

var longestCommonPrefix = function(strs = []) {
    // 如果字符串数组为空，则返回空字符串
    if (strs.length == 0) return ''
    // 取出第一个字符串作为基准前缀
    var firstStr = strs[0]
    for (var i = 1; i < strs.length; i++) {
      // 使用while控制基准字符串与字符串str[i]的公共前缀，如果当前字符串不是以基准前缀开头，逐渐缩短基准前缀的长度
      while (strs[i].indexOf(firstStr) !== 0) { // 为0时说明前缀匹配，继续比较后续字符串
        firstStr = firstStr.substring(0, firstStr.length - 1)
        if (firstStr == '') return '' // 如果基准前缀已经被缩短为空，则说明不存在公共前缀，没必要往后比较了，直接返回空字符串
      }
    }
    // 返回最终的结果
    return firstStr
}

最长公共前缀 ​

最长公共前缀