Java中如何查看最长公共前缀

在编程中，查找一组字符串的最长公共前缀是一个常见的问题。最长公共前缀是指一组字符串中所有字符串都共享的最长的前缀子串。例如，字符串数组 ["flower", "flow", "flight"] 的最长公共前缀是 "fl"。本文将介绍如何在Java中实现这一功能。

1. 问题分析

假设我们有一个字符串数组 strs，我们需要找到这个数组中所有字符串的最长公共前缀。如果数组为空，或者没有任何公共前缀，我们应该返回一个空字符串 ""。

2. 解决思路

我们可以采用以下步骤来解决这个问题：

1. 检查边界条件：如果数组为空，直接返回空字符串。
2. 选择基准字符串：通常选择数组中的第一个字符串作为基准字符串。
3. 逐个字符比较：遍历基准字符串的每个字符，与其他字符串的对应字符进行比较。
4. 停止条件：如果在某个字符上不匹配，或者某个字符串已经遍历完毕，则停止比较。
5. 返回结果：返回匹配的最长前缀。

3. 代码实现

以下是Java代码的实现：

public class LongestCommonPrefix {
    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        
        // 选择第一个字符串作为基准
        String prefix = strs[0];
        
        // 遍历基准字符串的每个字符
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            
            // 遍历数组中的其他字符串
            for (int j = 1; j < strs.length; j++) {
                // 如果当前字符串已经遍历完毕，或者字符不匹配
                if (i >= strs[j].length() || strs[j].charAt(i) != c) {
                    // 返回当前匹配的前缀
                    return prefix.substring(0, i);
                }
            }
        }
        
        // 如果所有字符都匹配，返回基准字符串
        return prefix;
    }

    public static void main(String[] args) {
        String[] strs = {"flower", "flow", "flight"};
        System.out.println("最长公共前缀: " + longestCommonPrefix(strs));
    }
}

4. 代码解析

• 边界检查：首先检查输入数组是否为空或长度为0，如果是，则直接返回空字符串。
• 基准字符串：选择数组中的第一个字符串作为基准字符串 prefix。
• 字符比较：遍历基准字符串的每个字符，与其他字符串的对应字符进行比较。
• 停止条件：如果某个字符串已经遍历完毕，或者字符不匹配，则返回当前匹配的前缀。
• 返回结果：如果所有字符都匹配，则返回基准字符串。

5. 示例运行

假设我们有以下输入：

String[] strs = {"flower", "flow", "flight"};

运行上述代码后，输出结果为：

最长公共前缀: fl

6. 复杂度分析

• 时间复杂度：假设数组中有 n 个字符串，每个字符串的平均长度为 m，那么时间复杂度为 O(n * m)。
• 空间复杂度：除了输入数组外，只使用了常数级别的额外空间，因此空间复杂度为 O(1)。

7. 总结

通过上述方法，我们可以有效地找到一组字符串的最长公共前缀。这种方法简单直观，适用于大多数情况。在实际应用中，我们可以根据具体需求对代码进行优化或扩展，例如处理特殊情况或提高性能。

希望本文对你理解如何在Java中查找最长公共前缀有所帮助！