力扣14 寻找字符串数组中最长公共前缀

力扣14 寻找字符串数组中最长公共前缀

题目：

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串

""

。

示例 1：

 输入：strs = ["flower","flow","flight"]

输出："fl" 

示例 2：

 输入：strs = ["dog","racecar","car"]

输出：""

解释：输入不存在公共前缀。 

提示：

• 1 <= strs.length <= 200

• 0 <= strs[i].length <= 200

• strs[i]

  仅由小写英文字母组成

解题思路：

首先我们需要将这个字符串数组进行排序，然后找到这个字符串数组中最短的字符串，因为进行循环比较的时候比较的次数不会超过最短的字符串的长度。进行排序后之后的数组我们仅仅比较第一个字符串与最后一个字符串即可。

代码：

 import java.util.Arrays;



/**

 * 返回一个字符串数组中的最长的公共前缀。

 * 首先我们可以对这个数组进行排序,然后比较排序之后的第一个字符串与最后一个字符串

 * 的元素是否相同,可以明确的是最多比较的次数是最短字符串的长度

 */

public class MaxLengthSubStrings {

    public static void main(String[] args) {

        String[] strings = {"abc","abcd","abdsc","abcwsed"};

        String s = maxLengthSubString(strings);

        System.out.println("s = " + s);

    }

    //定义一个方法获得最长的公共前缀,返回值类型为String参数为String[] str

    public static String maxLengthSubString(String[] str){

        if (str == null || str.length == 0) {

            return null;

        }

        if (str.length == 1) {

            return str[0];

        }

        int len = str.length;

        //对数组进行排序

        Arrays.sort(str);

        String firstStr = str[0];

        String lastStr = str[len - 1];

        //定义一个StringBuilder用来接收最长的公共前缀

        StringBuilder stringBuilder = new StringBuilder();

        //取得字符串数组中的最短字符串的长度

        int minLength = Math.min(firstStr.length(),lastStr.length());

        //判断第一个字符串与最后一个字符串相同的字符

        for (int i = 0; i < minLength; i++) {

            if(firstStr.charAt(i) == lastStr.charAt(i)){

                //如果字符相等就添加进stringBuilder

                stringBuilder.append(firstStr.charAt(i));

            }else {

                //否则就退出比较

                break;

            }

        }

        return stringBuilder.toString();

    }

}