专栏首页小浩算法《剑指offer》第14天:最长公共前缀

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

01、题目分析

首先还是看下题目:

题目14: 最长公共前缀

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

示例1:

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

示例 2:

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

解释:

  • 输入不存在公共前缀。

说明:

  • 所有输入只包含小写字母 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的最长公共前缀)

具体过程如下图所示:

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

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

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

03、代码分析

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

//GO
func 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 语言的版本:

//JAVA
class 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;
    }
}

运行结果:

本文分享自微信公众号 - 小浩算法(xuesuanfa),作者:程序员小浩

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 漫画:最长公共前缀题解(修订版)

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

    程序员小浩
  • 漫画:三次反转旋转数组

    第189题:给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

    程序员小浩
  • 漫画:三次反转旋转数组(一次修订版)

    第189题:给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

    程序员小浩
  • 最长公共前缀

    木子星兮
  • 自动补全不算什么,一键直达目录才是终极神器

    在命令行中切换目录是最常用的操作,不过很少有比一遍又一遍重复“cd ls cd ls cd ls ……”更令人沮丧的事情了。如果你不是百分百确定你想要进入...

    小小科
  • API设计的几条原则

    API 设计是微服务设计中非常重要的环节,代表服务之间交互的方式,会影响服务之间的集成。通常来说,一个好的 API 设计需要满足两个主要的目的。

    ThoughtWorks
  • 公交车线路查询系统

    逍遥剑客
  • linux 内存耗尽的分析

    在测试NAS性能,用fstest长时间写,分析性能变差的原因,发现server主机内存使用率很高。 1.首先查看内存 # top -M top - 14:...

    小小科
  • 压测工具swingbench和sysbench对比(r12笔记第13天)

    今天来说说两款压测工具sysbench,swingbench,早些时候傻傻分不清楚,其实两个差别大了去了。 swingbench 先来说说swingb...

    jeanron100
  • 如何设计API返回码(错误码)?

    客户端请求API,通常需要通过返回码来判断API返回的结果是否符合预期,以及该如何处理返回的内容等

    KenTalk

扫码关注云+社区

领取腾讯云代金券