编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 “”。
个人感觉纵向扫描方式比较直观,符合人类理解方式,从前往后遍历所有字符串的每一列,比较相同列上的字符是否相同,如果相同则继续对下一列进行比较,如果不相同则当前列不再属于公共前缀,当前列之前的部分为最长公共前缀。
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
}
-(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;
}
有序首尾比较法,先对数组进行排序,巧妙利用排序后的顺序及值之间的关系,只比较首尾两个字符串即可。
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
}
//有序首尾比较法
-(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;
}