leetcode14 最长公共前缀-纵向比较

本文主要是介绍leetcode14 最长公共前缀-纵向比较，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

示例

输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”

解析

纵向遍历：

func longestCommonPrefix(strs []string) string {if len(strs) == 0 {return ""}for i := 0; i < len(strs[0]); i++ { // 以字符串数组的第一个字符串为例for j := 1; j < len(strs); j++ { // 遍历字符串数组中的每个字符串if i == len(strs[j]) || strs[j][i] != strs[0][i] { // 两个终止条件：1.遍历到某个字符串的结尾；2.字符串该位置的值不相等return strs[0][:i]}}}return strs[0]
}

首先这道题没有特殊的算法，就是先遍历，但是遍历也可以氛围横向遍历和纵向遍历。纵向遍历上，可以以第一个字符串为参考，同时遍历所有字符串的每个字符，直到遇到某个字符串的结尾或者某两个字符不匹配则终止。

横向遍历：

func longestCommonPrefix(strs []string) string {if len(strs) == 0 {return ""}prefix := strs[0]count := len(strs)for i := 1; i < count; i++ {prefix = lcp(prefix, strs[i])if len(prefix) == 0 {break}}return prefix
}func lcp(str1, str2 string) string {length := min(len(str1), len(str2))index := 0for index < length && str1[index] == str2[index] {index++}return str1[:index]
}