LeetCode如何实现最长公共前缀

问题描述

给定一个字符串数组，要求找出这些字符串的最长公共前缀。

解题思路

要找出字符串数组的最长公共前缀，可以使用水平扫描法。首先，取数组中的第一个字符串作为最长公共前缀的初始值。然后，遍历数组中的每一个字符串，依次比较各个字符是否相等，直到遇到不相等的字符或者某个字符串的末尾。如果遍历完所有字符串都没有遇到不相等的字符，则当前的最长公共前缀为数组中的第一个字符串。如果在遍历过程中遇到了不相等的字符，或者某个字符串的末尾，说明最长公共前缀已经确定，即为当前字符串的前缀。

代码实现

public static String longestCommonPrefix(String[] strs) {
    if (strs == null || 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;
}

复杂度分析

假设数组中共有n个字符串，每个字符串的长度为m。

1. 时间复杂度：算法的时间复杂度为O(S)，其中S为所有字符串中字符的总数。最坏情况下，需要遍历所有字符串的所有字符，直到找到最长公共前缀的末尾或者某个字符串的末尾。
2. 空间复杂度：算法的空间复杂度为O(1)，只需要维护一个变量prefix来存储最长公共前缀。

综上所述，使用水平扫描法可以高效地找出字符串数组的最长公共前缀。