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我哦。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.08.01 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录