最长公共前缀

01、题目分析

首先还是看下题目:

题目14: 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,则返回””

示例1:

  1. 输入: ["flower","flow","flight"]
  2. 输出: "fl"

示例 2:

  1. 输入: ["dog","racecar","car"]
  2. 输出: ""

解释:

  • 输入不存在公共前缀。

说明:

  • 所有输入只包含小写字母 a-z

02、题解分析

我们要想寻找最长公共前缀,那么首先这个前缀是公共的,我们可以从任意一个元素中找到它。假定我们现在就从一个数组中寻找最长公共前缀,那么首先,我们可以将第一个元素设置为基准元素x0。假如数组为[“flow”,”flower”,”flight”],flow就是我们的基准元素x0。

然后我们只需要依次将基准元素和后面的元素进行比较(假定后面的元素依次为x1,x2,x3….),不断更新基准元素,直到基准元素和所有元素都满足最长公共前缀的条件,就可以得到最长公共前缀。

具体比对过程如下:

  • 如果strings.Index(x1,x) == 0,则直接跳过(因为此时x就是x1的最长公共前缀),对比下一个元素。(如flower和flow进行比较)
  • 如果strings.Index(x1,x) != 0, 则截取掉基准元素x的最后一个元素,再次和x1进行比较,直至满足string.Index(x1,x) == 0,此时截取后的x为x和x1的最长公共前缀。(如flight和flow进行比较,依次截取出flow-flo-fl,直到fl被截取出,此时fl为flight和flow的最长公共前缀)

具体过程如下图所示:

PNG

我们需要注意的是,在处理基准元素的过程中,如果基准元素和任一一个元素无法匹配,则说明不存在最长公共元素。

最后,我们记得处理一下临界条件。如果给定数组是空,也说明没有最长公共元素。

然后我们就可以开始写我们的代码了。

03、代码分析

根据分析,我们很容易得到下面的题解:

  1. //GO
  2. func longestCommonPrefix(strs []string) string {
  3. if len(strs) < 1 {
  4. return ""
  5. }
  6. prefix := strs[0]
  7. for _,k := range strs {
  8. for strings.Index(k,prefix) != 0 {
  9. if len(prefix) == 0 {
  10. return ""
  11. }
  12. prefix = prefix[:len(prefix) - 1]
  13. }
  14. }
  15. return prefix
  16. }

运行结果:

PNG

当然,我们也可以用分治法或者其他方法来解答这道题目。你可以自己尝试尝试哈。我们下期见!