如何实现最大公共前缀算法？

最大公共前缀(Longest Common Prefix)问题是求多个字符串的最大公共前缀。

我们可以使用横向扫描法实现最大公共前缀算法:

public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) return "";
    int minLen = Integer.MAX_VALUE;
    for (String str : strs) minLen = Math.min(minLen, str.length());

    int i = 0;
    while (i < minLen) {
        char c = strs[0].charAt(i);
        for (int j = 1; j < strs.length; j++) {
            if (strs[j].charAt(i) != c) return strs[0].substring(0, i); 
        }
        i++;
    }

    return strs[0].substring(0, minLen);
}

算法流程:

1. 获取所有字符串的最小长度 minLen。
2. 从左到右取每个字符 c,并与其他所有字符串当前位置的字符比较。
3. 如果相等,继续比较下一个位置。否则终止比较,返回结果。
4. 如果全部比较完成,返回 minLen 长度的公共前缀。
5. 特殊情况,如果 strs 为空数组,返回 “”。

时间复杂度 O(S),S为所有字符串中字符数之和,空间复杂度 O(1)。

所以,最大公共前缀的关键是:

1. 找到所有字符串的最小长度minLen,限定比较范围。
2. 从左到右逐个字符比较,如果当前位置字符相等,继续比较下一个位置。
3. 否则说明找到最大公共前缀,将该前缀返回。
4. 如果全部比较完成,返回minLen长度的前缀。
5. 特殊情况过滤。