《剑指offer》第14天：最长公共前缀

首先还是看下题目：

题目14: 最长公共前缀

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

示例1:

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

示例 2:

输入: ["dog","racecar","car"]输出: ""解释: 输入不存在公共前缀。

解释:

• 输入不存在公共前缀。
  说明：

• 所有输入只包含小写字母 a-z02、题解分析

我们要想寻找最长公共前缀，那么首先这个前缀是公共的，我们可以从任意一个元素中找到它。假定我们现在就从一个数组中寻找最长公共前缀，那么首先，我们可以将第一个元素设置为基准元素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的最长公共前缀）
  具体过程如下图所示：
  

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

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

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

题解可以很自然的给出，我们先给一个 go 的版本：

//GOfunc longestCommonPrefix(strs []string) string {    if len(strs) < 1 {        return ""    }    prefix := strs[0]    for _,k := range strs {        for strings.Index(k,prefix) != 0 {            if len(prefix) == 0 {                return ""            }            prefix = prefix[:len(prefix) - 1]        }    }    return prefix}

运行结果：

再给一个 java 语言的版本：

//JAVAclass Solution {    public String longestCommonPrefix(String[] strs) {        if (strs.length < 1 ) return "";        String prefix = strs[0];        for (String k : strs) {            while (k.indexOf(prefix) != 0) {                if (prefix.length() == 0) return "";                prefix = prefix.substring(0, prefix.length() - 1);            }        }        return prefix;    }}

运行结果：