首页 > 试题广场 >

最长公共前缀

[编程题]最长公共前缀
  • 热度指数：145400 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。

数据范围： ，
进阶：空间复杂度 O(1)，时间复杂度 O(n*len)
示例1

输入

["abca","abc","abca","abc","abcc"]

输出

"abc"
示例2

输入

["abc"]

输出

"abc"
算法知识视频讲解
添加回答
Java
进击小高头像 进击小高 
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)
Java
雾喔头像 雾喔
我的暴力解法： 
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)
Java
李克雷头像 李克雷 
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)
Java
牛客839384289号头像 牛客839384289号 
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)
Java
做则必成的勇气和信心头像 做则必成的勇气和信心 
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)
Java
neukfc头像 neukfc
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)
Java
牛客493951226号头像 牛客493951226号
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)
Java
云鸟头像 云鸟 
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)
Java
BlueProtocol头像 BlueProtocol 
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)
Java
默默努力的大鲨鱼头像 默默努力的大鲨鱼 
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)
Java
牛客用户007头像 牛客用户007
差点超时 
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)
Java
勇敢牛牛不怕难头像 勇敢牛牛不怕难 
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)
Java
超可爱超超头像 超可爱超超 


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)
Java
ITwolffy头像 ITwolffy 
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)
Java
lizi-hust头像 lizi-hust 
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)
Java
wjp-niuke头像 wjp-niuke
 
//可以跑出来 效率就不管了 哈哈哈

 public String longestCommonPrefix(String[] strs) {
        // write code here
        if (strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        //找到最短的字符串的长度
        int minLen = Integer.MAX_VALUE;
        for (int i = 0; i < strs.length; i++) {
            minLen = Math.min(minLen, strs[i].length());
        }

//逐列比较 end记录有不同字符的那一列的索引
        int end = 0;

        
        for (int i1 = 0; i1 < minLen; i1++) {
        //比较开关
            boolean coltf=true;
            for (int i = 0; i < strs.length-1; i++) {
                if (strs[i].charAt(i1)!= strs[i+1].charAt(i1)) {
                //某一列有相邻字符不相等时 ，开关置为false 内外层都break
                    coltf=false;
                    end=i1;
                    break;
                }

            }
            if( !coltf){

                break;
            }

            end++;

        }
        
        if (end==0) {
            return "";
        }
        return  strs[0].substring(0,end);


    }

发表于 2022-07-17 13:27:02 回复(0)
提交观点

问题信息

字符串
难度：
61条回答 20749浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号