给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。
数据范围： 
， %20%5Cle%205000%20)
进阶：空间复杂度 )
，时间复杂度 )
[编程题]最长公共前缀
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param strs string字符串一维数组
* @return string字符串
*/
public String longestCommonPrefix (String[] strs) {
// write code here
// 0.处理特殊情况
if (strs.length == 0) {
return "";
}
if (strs.length == 1) {
return strs[0];
}
// 1.按照长度从小到大给strs排序
Arrays.sort(strs, (s1, s2) -> s1.length() - s2.length());
// 2.从0位置开始检查strs中所有字符串的情况
int i = 0;
boolean flag = true;
while (i < strs[0].length() && flag) {
// i不越界且没发现不一致
char c = strs[0].charAt(i);
for (int j = 1; j < strs.length; j++) {
if (strs[j].charAt(i) != c) {
// 发现了不一致，则最长公共前缀为strs[0]的0 ~ i-1字符
flag = false;
break;
}
}
if (flag) {
// 若发现了不一致，则不必让i自增
i++;
}
}
// 3.截取strs[0]的0 ~ i-1字符返回
return strs[0].substring(0, i);
}
}
发表于 2024-11-17 16:04:42
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param strs string字符串一维数组
* @return string字符串
*/
public String longestCommonPrefix (String[] strs) {
// write code here
String res = "";
if(strs.length == 0){
return "";
}
if (strs.length == 1) {
return strs[0];
}
// 找到最短的字符串
String s1 = strs[0];
for(int i=0;i<strs.length-1;i++){
if(s1.length()>strs[i+1].length()){
s1 = strs[i+1];
}
}
// 遍历每个字符串，从第一个字符开始比较
for (int j = 0; j < s1.length(); j++) {
Boolean flag = false;
for (int i = 0; i < strs.length; i++) {
if(s1.charAt(j)==strs[i].charAt(j)){
flag = true;
}else{
flag = false;
break;
}
}
if(flag){
res += s1.charAt(j);
}
}
return res;
}
}
发表于 2024-08-29 11:07:03
回复(0)
public String longestCommonPrefix (String[] strs) {
// write code here
int n = strs.length;
String res = "";
if (n == 0) {
return "";
}
for (int i = 0; i < strs[0].length(); i++) {
boolean flag = true;
String tem = strs[0].substring(0, i + 1);
for (int j = 1; j < n; j++) {
flag = strs[j].contains(tem);
if (!flag) {
break;
}
}
if (flag) {
res = tem;
} else {
break;
}
}
return res;
}
发表于 2024-06-18 15:39:31
回复(0)
import java.util.*;
public class Solution {
public String longestCommonPrefix (String[] strs) {
if (strs == null || strs.length == 0)return "";
String pre=strs[0];
for(String str:strs){
while(!str.startsWith(pre)){
pre=pre.substring(0,pre.length()-1);
}
}
return pre;
}
}
编辑于 2024-04-19 11:42:35
回复(0)
我的暴力解法：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param strs string字符串一维数组
* @return string字符串
*/
public String longestCommonPrefix (String[] strs) {
if(strs.length==0)return "";
if(strs.length==1)return strs[0];
Arrays.sort(strs);
// write code here
String res=strs[0];
for(int i=1;i<strs.length;i++){
int n=0;
int min =Math.min(res.length(),strs[i].length());
while(n<min){
if(res.charAt(n)!=strs[i].charAt(n)){
res=res.substring(0,n);
break;
}
n++;
}
}
return res;
}
}
发表于 2024-04-03 14:19:28
回复(0)
public class Solution {
public String longestCommonPrefix (String[] strs) {
if (strs.length == 0) {
return "";
}
int n = 0;
while (n < strs[0].length()) {
char target = strs[0].charAt(n);
for (int i = 1; i < strs.length; i++) {
if (strs[i].length() <= n || strs[i].charAt(n) != target) {
return strs[0].substring(0, n);
}
}
n++;
}
return strs[0];
}
}
发表于 2023-11-10 17:06:57
回复(0)
public String longestCommonPrefix (String[] strs) {
// write code here
String str=strs.length==0?"":strs[0];
for(int i=0;i<str.length();i++){
for(int j=1;j<strs.length;j++){
if(strs[j].length()==i || str.charAt(i)!=strs[j].charAt(i)){
return strs[0].substring(0,i);
}
}
}
return str;
}
发表于 2023-06-11 15:53:42
回复(0)
public String longestCommonPrefix (String[] strs) {
if(strs.length==0) return "";
String tmp=strs[0];
for(int i=1;i<strs.length;i++){
while(strs[i].indexOf(tmp)!=0){//如果返回的索引位置不是0
tmp=tmp.substring(0,tmp.length()-1);
}
}
return tmp;//一直在缩短tmp,直至缩短到公共前缀
}
发表于 2023-05-02 23:00:47
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param strs string字符串一维数组
* @return string字符串
*/
//分治法，从中间切割成两个子字符串数组并递归比较，最后将问题转化成两个字符串之间求公共前缀的问题
public String longestCommonPrefix (String[] strs) {
// write code here
if (strs.length==0)
return "";
if (strs.length==1)
return strs[0];
return comparePerfix(Arrays.copyOfRange(strs, 0, strs.length / 2),
Arrays.copyOfRange(strs, strs.length / 2, strs.length))[0];
}
public String[] comparePerfix(String[] strArr1, String[] strArr2) {
String[] strs1, strs2;
if (strArr1.length == 1 && strArr2.length == 1) {
StringBuilder stringBuilder = new StringBuilder();
String str1 = strArr1[0], str2 = strArr2[0];
int n = Math.min(str1.length(), str2.length()), count = 0;
for (int i = 0; i < n; i++) {
if (str1.charAt(i) == str2.charAt(i)) {
stringBuilder.append(str1.charAt(i));
} else
break;
}
return new String[] {stringBuilder.toString()};
}
if (strArr1.length == 1)
strs1 = strArr1;
else
strs1 = comparePerfix(Arrays.copyOfRange(strArr1, 0, strArr1.length / 2),
Arrays.copyOfRange(strArr1, strArr1.length / 2, strArr1.length));
if (strArr2.length == 1)
strs2 = strArr2;
else
strs2 = comparePerfix(Arrays.copyOfRange(strArr2, 0, strArr2.length / 2),
Arrays.copyOfRange(strArr2, strArr2.length / 2, strArr2.length));
return comparePerfix(strs1, strs2);
}
}
发表于 2023-04-19 14:56:39
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param strs string字符串一维数组
* @return string字符串
*/
public String longestCommonPrefix (String[] strs) {
// write code here
if(strs==null||strs.length==0) return "";
int len=strs.length-1;
if(len==0) {
return strs[0];
}
int min=(int)Math.pow(2,31);
int index=0;
int mid=len/2;
for(int i=0;i<=mid;i++){
index=0;
for(int j=0;(strs[i].length())>j&&(strs[(len-i)].length())>j;j++){
if((strs[i].charAt(j))==(strs[(len-i)].charAt(j))) index++;
else break;
}
if(index<min) min=index;
if(i==mid) break;
}
return strs[0].substring(0,min);
}
}
发表于 2022-11-19 23:41:28
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param strs string字符串一维数组
* @return string字符串
*/
public String longestCommonPrefix (String[] strs) {
// write code here
//一共多少个字符串
int count = strs.length;
if(count == 0) return "";
if(count == 1) return strs[0];
//其中最短的长度
int minLength = strs[0].length();
for(int i = 0; i < count; i++){
minLength = Math.min(minLength, strs[i].length());
}
String lcp = "";
for(int i = 0; i < minLength; i++){
String temp = strs[0].substring(0, i + 1);//第一个字符串前i个字符
for(int j = 1; j < count; j++){
if(!strs[j].subSequence(0, i + 1).equals(temp)){
return lcp;
}
if(j == count - 1){
lcp = temp;
}
}
}
return lcp;
}
}
发表于 2022-10-25 21:21:28
回复(0)
public class Solution {
/**
*
* @param strs string字符串一维数组
* @return string字符串
*/
public String longestCommonPrefix(String[] strs) {
// write code here
if (strs == null ||strs.length == 0) {
return "";
}
int oneLength = strs[0].length();
// 遍历第一个字符串
for (int i = 0; i < oneLength; i++) {
// 遍历剩余的字符串
char temp = strs[0].charAt(i);
for (int j = 1; j < strs.length; j++) {
if (i == strs[j].length() || temp != strs[j].charAt(i)) {
return strs[0].substring(0, i);
}
}
}
return strs[0];
}
}
发表于 2022-10-09 10:06:06
回复(2)
import java.util.*;
public class Solution {
/**
*
* @param strs string字符串一维数组
* @return string字符串
*/
public String longestCommonPrefix (String[] strs) {
// write code here
StringBuilder sb = new StringBuilder();
if(strs.length == 0 || strs == null) return "";
if(strs.length == 1) return strs[0];
for (int i = 0; i < strs[0].length() ; i ++) {
char c = strs[0].charAt(i);
boolean flag = false;
for (int j = 0 ; j < strs.length ; j++) {
if(strs[j].length() - 1 < i){
flag = false;
break;
}
char temp = strs[j].charAt(i);
if ( c == temp ) {
flag = true;
} else {
flag = false;
break;
}
}
if (flag) sb.append(c);
else break;
}
return sb.toString();
}
}
发表于 2022-09-28 14:15:24
回复(0)
差点超时
import java.util.*;
public class Solution {
/**
*
* @param strs string字符串一维数组
* @return string字符串
*/
public String longestCommonPrefix (String[] strs) {
// write code here
if (strs.length == 1) return strs[0];
if (strs.length == 0) return "";
String index = strs[0];
for (int i = index.length() - 1; i >= 0; i--) {
boolean tag = true;
for (int j = 1; j < strs.length; j ++) {
if (!strs[j].startsWith(index.substring(0, i + 1))) {
tag = false;
}
}
if (tag == true) {
return index.substring(0, i + 1);
}
}
return "";
}
}
发表于 2022-09-04 15:23:47
回复(0)
import java.util.*;
public class Solution {
/**
*
* @param strs string字符串一维数组
* @return string字符串
*/
public String longestCommonPrefix (String[] strs) {
// write code here
if(strs.length==0){
return "";
}
Arrays.sort(strs);
String first=strs[0];
String last=strs[strs.length-1];
int index1=0;
int index2=0;
while(index1<first.length()&&index2<last.length()){
if(first.charAt(index1)==last.charAt(index2)){
index1++;
index2++;
}else{
break;
}
}
return first.substring(0,index1);
}
}
发表于 2022-08-25 19:04:17
回复(0)
import java.util.Arrays;
public class BM84 {
public static void main(String[] args) {
String s = getLongCommonString2(new String[]{"abca", "abc", "abca", "abc", "abcc"});
System.out.println("s = " + s);
}
public static String longestCommonPrefix(String[] strs) {
// write code here
/**
* 拿出第一个字符串
*
* 双重遍历,外层数组长度 限时条件数组
* 内层每一个字符串长度 限制条件数组长度和每个字符串长度
*
* 判断前缀是否相等,相等
*/
if (strs.length == 0) {
return "";
}
Arrays.sort(strs);
String head = strs[0];
String tail = strs[strs.length - 1];
int i = 0;
int len = Math.min(head.length(), tail.length());
for (i = 0; i < len && head.charAt(i) == tail.charAt(i); i++) {
}
return head.substring(0, i);
}
/**
* 方法一:水平查找
*/
public static String getLongCommonString1(String[] str) {
if (str.length == 0) {
return "";
}
String fix = str[0];
for (int i = 1; i < str.length; i++) {
fix = getFix(fix, str[i]);
}
return fix;
}
public static String getFix(String fix, String str) {
if (fix.isEmpty() || str.isEmpty()) {
return "";
}
StringBuilder stringBuilder = new StringBuilder();
int len = Math.min(fix.length(), str.length());
for (int i = 0; i < len; i++) {
if (fix.charAt(i) == str.charAt(i)) {
stringBuilder.append(fix.charAt(i));
} else {
return stringBuilder.toString();
}
}
return stringBuilder.toString();
}
/**
* 方法二,垂直查找
*/
public static String getLongCommonString2(String[] str) {
if (str.length == 0) {
return "";
}
String fix = str[0];
int target = 0;
for (int i = 0; i < fix.length(); i++) {
int index = 0;
for (int j = 1; j < str.length && i < str[j].length(); j++) {
if (fix.charAt(i) == str[j].charAt(i)) {
index++;
} else {
break;
}
}
if (index == str.length - 1) {
target++;
System.out.println(target);
}
}
return fix.substring(0, target);
}
/**
* 方法三 按字典顺序排序 两个有公共前缀的字符串中间出现的字符串必有和这两个一样的公共1前缀
*/
public static String getLongCommonString3(String[] str) {
if (str.length == 0) {
return "";
}
Arrays.sort(str);
String start = str[0];
String end = str[str.length - 1];
int len = Math.min(start.length(), end.length());
int i;
for (i = 0; i < len && start.charAt(i) == end.charAt(i); i++) {
}
return start.substring(0, i);
}
}
发表于 2022-08-24 00:46:36
回复(0)
import java.util.*;
public class Solution {
public String longestCommonPrefix (String[] strs) {
if (strs.length == 0 || strs == null) return "";
//字典序排序
Arrays.sort(strs);
//比较第一个和最后一个
String first = strs[0];
String last = strs[strs.length - 1];
for (int i = 0; i < first.length(); i++) {
if (first.charAt(i) != last.charAt(i)) {
return first.substring(0, i);
}
}
//否则返回最短的第一个字符串
return first;
}
}
发表于 2022-07-29 12:34:20
回复(0)
import java.util.*;
public class Solution {
public String longestCommonPrefix (String[] strs) {
int n = strs.length;
if(n==0) return "";
int len = strs[0].length();
String res = "";
for(int i=0; i<len; i++){
char c = strs[0].charAt(i);
for(int j=1; j<n; j++){
if(i==strs[j].length() || strs[j].charAt(i)!=c) return res;
}
res += c;
}
return res;
}
}
发表于 2022-07-23 09:55:01
回复(0)
问题信息
难度：
64条回答
668收藏
21951浏览
通过挑战的用户
查看代码-
2022-10-31 17:02:28 -
2022-09-16 17:56:23
-
2022-09-16 17:19:08
-
2022-09-16 16:29:16
-
2022-09-16 16:13:24
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
