最长公共前缀

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

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

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 仅由小写英文字母组成

最长公共前缀

思路：我们可以将字符串数组按照natural ordering排序，取数组最大和最小的字符串，从左至右，比较每个字符，从而找到最长公共前缀

public class LongestCommonPrefix {

    public static String findLongestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        if (strs.length == 1) {
            return strs[0];
        }

        List<String> strList = Arrays.asList(strs);
        Collections.sort(strList);

        String leftStr = strList.get(0);
        String rightStr = strList.get(strList.size() - 1);
        StringBuilder commonPrefix = new StringBuilder();
        int index = 0;
        int maxIndex = Math.min(leftStr.length(), rightStr.length()) - 1;
        if (maxIndex < 0) {
            return "";
        }

        while (leftStr.charAt(index) == rightStr.charAt(index)) {
            char c = leftStr.charAt(index);
            commonPrefix.append(c);
            index ++;
            if (index > maxIndex) {
                break;
            }
        }
        return commonPrefix.toString();
    }
}