字符串的最长公共前缀

需求：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串。

示例 1:

输入: ["flower","flow","flight"]

输出: "fl"

示例 2:

输入: ["dog","racecar","car"]

输出: ""

一、实现思路

1. 获取第一个index的字符做为原始前缀，比如：flower。

2. 第一次遍历获取每一个字符串，比如分别获区flower，flow，flight。

3. 第二次遍历分别截取字符串减一的长度与原始前缀做比较。

4. 每次第二次遍历每次遍历对原始前缀进行缩减。

5. 循环2～3步骤，如果不存在前缀，返回空字符串，存在返回前缀。

二、代码实现

public class LongestCommonPrefix {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";

        // 以数组中的第一个字符串作为起始比较基准
        String prefix = strs[0];

        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                // 缩短前缀长度
                prefix = prefix.substring(0, prefix.length() - 1);
                // 如果前缀为空，则没有公共前缀
                if (prefix.isEmpty()) return "";
            }
        }
        return prefix;
    }

    public static void main(String[] args) {
        LongestCommonPrefix lcp = new LongestCommonPrefix();
        String[] input1 = {"flower", "flow", "flight"};
        System.out.println("Example 1: " + lcp.longestCommonPrefix(input1));
        String[] input2 = {"dog", "racecar", "car"};
        System.out.println("Example 2: " + lcp.longestCommonPrefix(input2));
    }
}