专栏首页灵魂画师牧码画解算法:14. 最长公共前缀

画解算法:14. 最长公共前缀

题目链接

https://leetcode-cn.com/problems/longest-common-prefix/

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 ""。

示例 1:

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

示例 2:

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

说明:

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

解题方案

思路

  • 标签:字符串
  • 当字符串数组长度为0时则公共前缀为空,直接返回
  • 令最长公共前缀ans的值为第一个字符串,进行初始化
  • 遍历后面的字符串,依次将其与ans进行比较,两两找出公共前缀,最终结果即为最长公共前缀
  • 如果查找过程中出现了ans为空的情况,则公共前缀不存在直接返回
  • 时间复杂度:O(s),s为所有字符串的长度之和

代码

  • Java版本
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0) 
            return "";
        String ans = strs[0];
        for(int i =1;i<strs.length;i++) {
            int j=0;
            for(;j<ans.length() && j < strs[i].length();j++) {
                if(ans.charAt(j) != strs[i].charAt(j))
                    break;
            }
            ans = ans.substring(0, j);
            if(ans.equals(""))
                return ans;
        }
        return ans;
    }
}
  • JavaScript版本
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    if(strs.length == 0) 
        return "";
    let ans = strs[0];
    for(let i =1;i<strs.length;i++) {
        let j=0;
        for(;j<ans.length && j < strs[i].length;j++) {
            if(ans[j] != strs[i][j])
                break;
        }
        ans = ans.substr(0, j);
        if(ans === "")
            return ans;
    }
    return ans;
};

画解

本文分享自微信公众号 - 牧码啦(mumalo),作者:灵魂画师牧码

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

原始发表时间:2019-06-12

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 画解算法 171-Excel表列序号

    https://leetcode-cn.com/problems/excel-sheet-column-number/

    灵魂画师牧码
  • 画解算法:771. 宝石与石头

    https://leetcode-cn.com/problems/jewels-and-stones/

    灵魂画师牧码
  • 画解算法 674-最长连续递增序列

    https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/

    灵魂画师牧码
  • CES 2018前瞻丨AI、自动驾驶将备受关注,VR/AR势头依然不弱

    VRPinea
  • ROS机器人程序设计(原书第2版)补充资料 (壹) 第一章 ROS系统入门

    书中,大部分出现hydro的地方,直接替换为indigo或jade或kinetic,即可在对应版本中使用。

    zhangrelay
  • 为什么“少就是多”是云计算的秘密

    正如云计算通常将硬件和整个物理层抽象化一样,云原生计算将此原则扩展到所有内部环境。因此,云原生方法是混合IT的基础,它试图抽象多个公共云、私有云、内部虚拟化和遗...

    静一
  • ROS机器人高效编程(原书第3版)勘误、问题及资料汇总

    补充一行代码装ROS,适用于14.04LTS(indigo)和16.04LTS(Kinetic):

    zhangrelay
  • 你应该知道的 @ConfigurationProperties 注解的使用姿势,这一篇就够了

    在编写项目代码时,我们要求更灵活的配置,更好的模块化整合。在 Spring Boot 项目中,为满足以上要求,我们将大量的参数配置在 application.p...

    JAVA葵花宝典
  • Hibernate学习总结

    Hibernate的视频溜了一遍,里面涉及到得内容并不多,不过个人感觉其复杂度还是比较高的,相比于Struts来说。

    the5fire
  • 数字资产场外交易币币交易平台开发的公司

    传统的数字资产交易平台就是我们知道的撮合交易,这种模式主要是法币与数字资产之间的直接交易。如果你想要投资数字资产,只需要充值资金在账户,然后用账户的里的资金直接...

    v13823115027

扫码关注云+社区

领取腾讯云代金券