leetcode【14题】Longest Common Prefix

题目:Longest Common Prefix

内容:

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

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

理解题目:

  如数组 ["a", "b"]   最长的公共前缀字符串是 “”;

  如数组 ["aa", "aa"]   最长的公共前缀字符串是 “aa”;

  如数组 ["abc", "abcd"]   最长的公共前缀字符串是 “abc”。。。

解题思路

1 1 如果数组为空,则最长公共前缀为"";
2 
3 2 如果数组不为空:
4 (1)找出字符串数组中长度最短的字符串min,其长度为min_len; 因为最长的公共前缀长度不会超过min_len;
5 (2)遍历数组,将min位置为[i] 的字符 和 数组中其他字符串位置为[i]的字符 比较;
6         如果不相等,则最长公共前缀为 min的前i个字符;
7         如果都相等,则最长公共前缀为 min。

Go语言实现

 1 func longestCommonPrefix(strs []string) string {
 2     
 3     if len(strs) == 0 {
 4         return ""
 5     }
 6     
 7     min_len := len(strs[0])
 8     index := 0
 9     for i:=0; i<len(strs); i++ {
10         if len(strs[i]) < min_len {
11             min_len = len(strs[i])
12             index = i
13         }
14     }
15     
16     for j:=0; j<len(strs[index]); j++ {
17         for k:=0; k<len(strs); k++ {
18             if strs[index][j] != strs[k][j]{
19                  return strs[index][:j]
20             }
21         }
22     }
23     return strs[index]  
24 }

看一下耗时:

Python3实现

 1 class Solution:
 2     def longestCommonPrefix(self, strs):
 3         """
 4         :type strs: List[str]
 5         :rtype: str
 6         """
 7         if not strs:
 8             return ""
 9         shortstr = min(strs, key=len)
10         for i, cha in enumerate(shortstr):
11             for other in strs:
12                 if other[i] != cha:
13                     return shortstr[:i]
14         return shortstr

看一下耗时:

是不是感觉go要快很多,Python更优雅?

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏测试开发架构之路

C++之类和对象的使用(三)

对象数组 如果构造函数只有一个参数,在定义数组时可以直接在等号后面的花括号内提供。Student stud[3]={90,92,01};//合法 如果构造函数...

3419
来自专栏java思维导图

正则表达式思维导图,不再难懂

01 一张思维导图 ? 02 导图内容解析 工具 RegexBuddy 语法结构 字符 [ab5@] 匹配"a"或"b"或"5"或"@" [^abc] 匹配a、...

42111
来自专栏Esofar 开发日记

JavaScript权威指南 - 数组

JavaScript数组是一种特殊类型的对象。 JavaScript数组元素可以为任意类型,最大容纳232-1个元素。 JavaScript数组是动态的,有...

914
来自专栏Python爬虫实战

Python数据类型之数字类型

输入1就会显示1,我们怎么知道1就是整数类型呢?在Python里面有一个type()函数,它能告诉我们所代表的类型。

1332
来自专栏软件开发 -- 分享 互助 成长

C++ 隐式类型转换

C++定义了一组内置类型对象之间的转换标准,在必要的时候它们被编译器隐式的转换 1、任何两种或多种类型的数据和变量混合操作的时候,最宽的数据类型成为目标转换类型...

2257
来自专栏猿人谷

static_cast ,reinterpret_cast

用法:static_cast < type-id > ( expression ) 该运算符把expression转换为type-id类型,但没有运行时类型检查...

22710
来自专栏Java成长之路

多态易错题

①②③比较好理解,一般不会出错。④⑤就有点糊涂了,为什么输出的不是”B and B”呢?!!先来回顾一下多态性。

1062
来自专栏北京马哥教育

Python数据类型知识点全解

作者:zhang_derek 1.字符串 字符串常用功能 name = 'derek' print(name.capitalize()) #首字母大写 ...

3045
来自专栏Nian糕的私人厨房

JavaScript 常见面试题分析(一)

这道题考察的是 JS 的变量类型,JS 的变量类型有值类型和变量类型两种,值类型包括 undefined、字符串、数字、布尔值,引用类型包括对象、数组、函数

854
来自专栏小白的技术客栈

Python之解析式您知多少?

解析式 解析式 今天给大家介绍Python中的解析式。 ? 解析式简单介绍 解析式, 列表解析 # Python2只有列表解析 生成器解析 # Python...

4515

扫码关注云+社区

领取腾讯云代金券