力扣题目学习笔记(OC + Swift) 14. 最长公共前缀
2023-12-20 12:37:33
14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 “”。
方法一 竖向扫描法
个人感觉纵向扫描方式比较直观,符合人类理解方式,从前往后遍历所有字符串的每一列,比较相同列上的字符是否相同,如果相同则继续对下一列进行比较,如果不相同则当前列不再属于公共前缀,当前列之前的部分为最长公共前缀。
Swift
func longestCommonPrefix(_ strs: [String]) -> String {
guard let firstStr = strs.first, !firstStr.isEmpty else { return "" }
for i in 0..<firstStr.count {
for j in 1..<strs.count {
if strs[j].count == i || strs[j][strs[j].index(strs[j].startIndex, offsetBy: i)] != firstStr[firstStr.index(firstStr.startIndex, offsetBy: i)] {
return String(firstStr.prefix(i))
}
}
}
return firstStr
}
OC
-(NSString *)longestCommonPrefix:(NSArray <NSString *>*)strs {
if (strs.count <= 0) {
return @"";
}
NSString *firstStr = strs.firstObject;
NSInteger len = firstStr.length;
for (NSInteger i=0; i<len; i++) {
for (NSInteger j=1; j<strs.count; j++) {
if (strs[j].length == i || [strs[j] characterAtIndex:i] != [firstStr characterAtIndex:i]) {
return [firstStr substringToIndex:i];
}
}
}
return firstStr;
}
方法二 有序首尾比较法
有序首尾比较法,先对数组进行排序,巧妙利用排序后的顺序及值之间的关系,只比较首尾两个字符串即可。
Swift
func longestCommonPrefix(_ strs: [String]) -> String {
let strs = strs.sorted()
let start = strs.first!
let end = strs.last!
var res = ""
for i in 0..<start.count {
let s = start[start.index(start.startIndex, offsetBy: i)]
if s == end[end.index(end.startIndex, offsetBy: i)]{
res.append(s)
}else {
break
}
}
return res
}
OC
//有序首尾比较法
-(NSString *)longestCommonPrefix:(NSArray *)strs {
NSArray *sortedStrs = [strs sortedArrayUsingComparator:^NSComparisonResult(NSString *obj1, id _Nonnull obj2) {
return [obj1 compare:obj2 options:NSCaseInsensitiveSearch];
}];
NSString *res = @"";
NSString *firstStr = sortedStrs.firstObject;
NSString *lastStr = sortedStrs.lastObject;
for (NSInteger i=0; i<firstStr.length; i++) {
if ([firstStr characterAtIndex:i] == [lastStr characterAtIndex:i]) {
unichar c = [firstStr characterAtIndex:i];
res = [res stringByAppendingString:[NSString stringWithCharacters:&c length:1]];
}else {
break;
}
}
return res;
}
文章来源:https://blog.csdn.net/zzl819954692/article/details/135061782
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!