Swift 最长公共前缀 - LeetCode

LeetCode.jpg

题目: 最长公共前缀

描述:

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

案例1:

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

案例2:

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

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

方案一:将字符串转为[Character],第一个和第二个求最长前缀,前缀和第三个求最长前缀...
代码一:
func longestCommonPrefix(_ strs: [String]) -> String {
    
    if strs.isEmpty { return "" }
    if strs.count == 1 {
        return strs.first!
    }
    //将[String] -> [[Character]]
    var chars = strs.map{str in Array(str)}
    
    //求两个[Character] 的公共前缀
    func twoLongestCommonPrefix(_ str1: [Character], str2: [Character]) ->  [Character] {
        var index = 0
        var temp1 = [Character]()
        while index < str1.count && index < str2.count {
            if str1[index] == str2[index] {
                temp1.append(str1[index])
                index += 1
            } else {
                break
            }
        }
        return temp1
    }
    
    var temp = chars[0]
    for i in 1..<chars.count {
        if temp.isEmpty {
            break
        }
        temp = twoLongestCommonPrefix(temp, str2: chars[i])
        print(temp)
    }
    
    return String(temp)
}
执行用时:28ms
方案二:取出第一个字符串,使用后面的字符串判断第一个字符串是否是他们的前缀,不是则将第一个字符串长度减一,继续判断
代码二:
func longestCommonPrefix(_ strs: [String]) -> String {
    let count = strs.count
    
    if count == 0 {
        return ""
    }
    if count == 1 {
        return strs.first!
    }
    
    var result = strs.first!
    for i in 1..<count {
        while !strs[i].hasPrefix(result) {
            result = String(result.prefix(result.count - 1))
            if result.count == 0 {
                return ""
            }
        }
    }
    return result
}
执行用时:16ms

开始我想的是如果字符串长度是无序的,那么把字符串变为有序是可以提升效率的,所以我加了如下代码 进行排序

let s = strs.sorted{$0.count < $1.count}

但实际测试发现,效率并未提升、、、我忽略了排序的时间、、、、尴尬了

用Swift开始学习算法中,在LeetCode中开始做初级算法这一章节,将做的题目在此做个笔记,希望有更好方法同学们cue我哦。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏诸葛青云的专栏

C语言什么是结构体?初步学习C语言结构体三部曲

结构体部分内容,涉及结构体定义,结构体变量,结构体指针,结构体数组,更多内容敬请关注。

1523
来自专栏我和PYTHON有个约会

18. 再说循环~列表和循环的高级操作

在前面的课程中,我们已经学习了循环和函数的基本操作,这节内容主要针对循环和函数在项目使用过程中的一些更加有使用价值的操作进行分析和讲解

741
来自专栏达摩兵的技术空间

a>b的那些事

经常会遇到对比两个值大小关系的逻辑,常规的处理中我们都是处理两个数字或者数字类型的字符串。那么这里进行延伸拓展的练习,来避免一些开发中的采坑。

681
来自专栏云霄雨霁

排序----堆排序

1610
来自专栏Java与Android技术栈

借助Java 8实现柯里化借助Java 8实现柯里化柯里化的好处总结

在函数式编程中,函数的概念跟数学中函数的概念是一样的,类似于“映射”。高阶函数和柯里化是函数式编程的特性。

1312
来自专栏Vamei实验室

Python基础09 面向对象的进一步拓展

我们熟悉了对象和类的基本概念。我们将进一步拓展,以便能实际运用对象和类。 调用类的其它信息 上一讲中提到,在定义方法时,必须有self这一参数。这个参数表示某个...

2056
来自专栏Python小屋

Python中的偏函数和函数柯里化

偏函数(partial)和函数柯里化(currying)是函数式编程中常用的技术。有时候我们在复用已有函数时可能需要固定其中的部分参数,这除了可以通过默认值参数...

3004
来自专栏Vamei实验室

Python基础09 面向对象的进一步拓展

我们熟悉了对象和类的基本概念。我们将进一步拓展,以便能实际运用对象和类。 调用类的其它信息 上一讲中提到,在定义方法时,必须有self这一参数。这个参数表示某个...

2007
来自专栏技术小站

(String)、toString、String.valueOf用法区别(转)

在Java项目的实际开发和应用中,常常需要用到将对象转为String这一基本功能。本文将对常用的转换方法进行一个总结。

1152
来自专栏JetpropelledSnake

Python入门之面向对象编程(一)面向对象概念及优点

本文分为如下几个部分 首先说明面向对象是什么,然后结合实际例子说明面向对象的如下几个优点 方便函数管理 数据封装 对象操作 最后总结一下面向对象的好处 概念...

3777

扫码关注云+社区

领取腾讯云代金券