[数据结构与算法]LeetCode14

最长公共前缀

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

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

示例 1：

输入：strs = [“flower”,“flow”,“flight”]
输出：“fl”

思路
/**
*最长公共前缀
* 数组排序，（按照字典排序）会得到如下特性
* 如果存在公共前缀则 第一个字符串 和最后一个字符串中包含整个字符数组的最长公共前缀，
* 如果不存在公共前缀 则第一个字符串和最后一个字符串 中没有公共的前缀
*
* 则按照这个特性可以直接得出结果
* 首先使用数排序，满足以上特性
* 然后计算第一个字符和最后一个字符长度 中最小的字符长度 。即得到最大循环判断的数值 （公共前缀在最小的字符长度中）
* 使用循环判断第一个字符串与最后一个字符串中 公共前缀有多少
* 得到 i 后
* 返回第一个字符串 0 到 i 的字母 就是整个数组中的最长公共前缀
*
* 时间复杂度为：o(nlogn)(排序) + o(n)（找公共前缀） = o(nlog n)
* 空间复杂度：o(1);没有使用额外空间
*
*/

代码

public static String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return strs[0];
        }
        Arrays.sort(strs);//排序
        String st = strs[0];
        String ed = strs[strs.length - 1];
        int len = st.length() >= ed.length() ? ed.length() : st.length();
        int i = 0;
        for (; i < len; i++) {
            if (st.charAt(i) != ed.charAt(i)) {
                break;
            }
        }
        return st.substring(0, i);
    }