Java每日一题——最长公共前缀_java 给你一个大小为n的字符串数组strs查找最长公共前缀

一、题目描述

给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。

数据范围： 0 \le n \le 50000≤n≤5000， 0 \le len(strs_i) \le 50000≤len(strsi​)≤5000

进阶：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

示例1

输入：["abca","abc","abca","abc","abcc"]

返回值："abc"

示例2

输入：["abc"]

返回值："abc"

题目链接：

最长公共前缀_牛客题霸_牛客网

二、解题思路

 找出两个字符串的最长公共前缀，用找出的字符串再与下一个字符串找，最终得到的字符串即为字符串数组中的最长公共前缀。

三、代码

import java.util.*;
 
public class Solution {
    
    public String twoLLongestCommonPrefix (String str1,String str2){    //找出两个字符串的最长公共前缀
        int length=str1.length()>str2.length()?str2.length():str1.length();    //找出短的字符串长度
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<length;i++){    //相同的提取出来，遇到不同的直接结束循环
            if(str1.charAt(i)==str2.charAt(i)){
                sb.append(str1.charAt(i));
            }else{
                break;
            }
        }
        String str=sb.toString();
        return str;
    }
    
    
    public String longestCommonPrefix (String[] strs) {
        if(strs.length==0){
            return "";
        }
        for(int i=0;i<strs.length-1;i++){
            String str=twoLLongestCommonPrefix(strs[i],strs[i+1]);    //找出两个字符串的最长公共前缀
            strs[i+1]=str;    //用找出的字符串再与下一个字符串找
        }
        return strs[strs.length-1];
    }
}