专栏首页爱写BugLeetcode 14:Longest Common Prefix 最长公共前缀

Leetcode 14:Longest Common Prefix 最长公共前缀

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

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

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

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

说明:

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

解题思路Java:

很简单又很经典的一道题,我的思路起先是 把第字符串组第一个字符串转为char型。利用StringBuilder逐一累加相同字符。由于字符串长度不一,可以先遍历找出最小长度字符串,这里我选择抛错的形式,减少一次 找出最小长度字符串 的遍历。

代码:

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int strLen=strs.length;
        if(strLen==0) return "";//空字符串组返回""
        char[] temp=strs[0].toCharArray();
        StringBuilder str = new StringBuilder();
        for (int i=0;i<strs[0].length();i++){//以第一个字符串长度开始比较
            for (int j=1;j<strLen;j++){
                try {
                    if(temp[i]!=strs[j].charAt(i)){
                        return str.toString();
                    }
                }catch (IndexOutOfBoundsException e){//抛出错误,这里错误是指索引超出字符串长度
                    return strs[j];
                }
            }
            str.append(temp[i]);
        }
        return strs[0];
    }
}

后面想到Java有 subString() 方法,可指定长度截取字符串,无需转为 char[] 型,但是在 Leetcode 提交时反而不如上面这种方式运算快,这也说明了Java不支持运算符重载,使用 substring() 每次新建一个String字符串,效率并不高。

最后看到一个方法,大致思路是找到最小长度字符串,从大到小截取字符串,既然用到 subString() 方法,不如就从后向前,因为题目是找出最长公众前缀,从大到小效率很高。具体请看:

 public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length==0) return "";
        int min=Integer.MAX_VALUE;
        String minStr="";
        for(int i=0;i<strs.length;i++){//找出最小长度字符串
            if(min>strs[i].length()){
                minStr=strs[i];
                min=strs[i].length();
            }
        }
        if(min==0) return "";
        for(int i=min;i>=0;i--){//最小长度字符串从长到短截取
            String standard=minStr.substring(0, i);
            int j=0;
            for(j=0;j<strs.length;j++){
                if(strs[j].substring(0, i).equals(standard)) continue;
                else break;
            }
            if(j==strs.length) return standard;
        }
        return "";
    }
}

原代码链接:https://blog.csdn.net/qq_14927217/article/details/72955791

解题思路py3:

再次投机取巧,os.path 封装函数 commonprefix() 一步到位。

代码:

class Solution(object):
    def longestCommonPrefix(self, strs):
        import os
        return os.path.commonprefix(strs)

其实该函数是利用ASCll码比较的特性来编写的,源码:

def commonprefix(m):
    "Given a list of pathnames, returns the longest common leading component"
    if not m: return ''
    # Some people pass in a list of pathname parts to operate in an OS-agnostic
    # fashion; don't try to translate in that case as that's an abuse of the
    # API and they are already doing what they need to be OS-agnostic and so
    # they most likely won't be using an os.PathLike object in the sublists.
    if not isinstance(m[0], (list, tuple)):
        m = tuple(map(os.fspath, m))
    s1 = min(m)
    s2 = max(m)
    for i, c in enumerate(s1)://枚举得到s1的每一个字符及其索引
        if c != s2[i]:
            return s1[:i]
    return s1

尽管如此,py3这段代码的执行速度依然远比Java慢的多。

注:ASCll码比较大小并非是按照所有字符的ASCll累加之和比较,是从一个字符串第一个字符开始比较大小,如果不相同直接得出大小结果,后面的字符不在比较。所以利用这个特性,找到ASCll码最小的字符串与ASCll码最大字符串,直接匹配两个字符串前缀既可得到最长公共前缀。

本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写Bug

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • # Leetcode 14:Longest Common Prefix 最长公共前缀

    Write a function to find the longest common prefix string amongst an array of st...

    爱写bug
  • Manjaro安装配置美化字体模糊发虚解决记录

    或者google拼音:第一行改成sudo pacman -S fcitx-googlepinyin,谷歌拼音的话,如果全部安装了依赖,可以在包管理卸载qt5那几...

    爱写bug
  • LeetCode 29:验证二叉搜索树 Validate Binary Search Tree

    Given a binary tree, determine if it is a valid binary search tree (BST).

    爱写bug
  • # Leetcode 14:Longest Common Prefix 最长公共前缀

    Write a function to find the longest common prefix string amongst an array of st...

    爱写bug
  • 【LeetCode】(No.014)最长公共前缀

    最长公共前缀指的是字符串数组中所有公共最长的前缀。 如果是空串的话,那么说明前缀就是“” 如果都是以“ ”开头的,那么就是“ ” 然后最长的前缀不会超过最短的字...

    PM小王
  • Python函数(一)之杵臼之交

    函数的结构:       def 函数名():             函数体             return语句

    py3study
  • 人人都能学会的python编程教程12:函数的参数

    Python的函数定义非常简单,也非常灵活。除了正常定义的必选参数外,还可以使用默认参数、可变参数和关键字参数,使得函数定义出来的接口,不但能处理复杂的参数,还...

    JKXQJ
  • 宝宝都能学会的python编程教程12:函数的参数

    Python的函数定义非常简单,也非常灵活。除了正常定义的必选参数外,还可以使用默认参数、可变参数和关键字参数,使得函数定义出来的接口,不但能处理复杂的参数,还...

    JKXQJ
  • 干货|一文搞定pandas中数据合并

    在实际处理数据业务需求中,我们经常会遇到这样的需求:将多个表连接起来再进行数据的处理和分析,类似SQL中的连接查询功能。

    刘早起
  • python 引用传递和值传递详解(实参,形参)

    python中函数参数是引用传递(不是值传递)。对于不可变类型,因变量不能被修改,所以运算时不会影响到变量本身;而对于可变类型来说,函数体中的运算有可能会更改传...

    砸漏

扫码关注云+社区

领取腾讯云代金券