Java基础搜索解答

Question

3、最长公共前缀（输入一个字符串数组，查找该数组中所有字符串的最长公共前缀，并将其输出，如果不存在公共前缀，输出“NO”）。
输入格式：
第一行一个整数 n 代表数组长度。
往下 n 行，每行一个字符串
输出格式：
共一行，为最长公共前缀或“NO”。

Answer 1

引自免费微信小程序：皆我百晓生

要解决这个问题，我们可以使用 Java 编写一个函数，这个函数接受一个字符串数组作为参数，然后找到所有字符串的最长公共前缀。下面是详细的步骤和代码实现：

1. 首先，我们需要确定数组中的第一个字符串作为参考字符串，因为所有的公共前缀都至少包含这个字符串的所有字符。
2. 然后，遍历这个参考字符串的每个字符，对于每一个字符，检查其他所有字符串在相同位置是否也含有相同的字符。如果有任何一个字符串不匹配，则停止搜索并返回当前已找到的公共前缀。
3. 如果我们成功地比较了参考字符串的所有字符，那么这些字符就是最长公共前缀。
4. 如果在任何时刻没有找到公共前缀，即所有字符串在某个位置都不匹配，我们可以提前结束搜索并返回 "NO"。

以下是完整的 Java 代码实现：

import java.util.Scanner;

public class LongestCommonPrefix {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String[] strings = new String[n];
        
        for (int i = 0; i < n; i++) {
            strings[i] = scanner.next();
        }
        
        System.out.println(longestCommonPrefix(strings));
        
        scanner.close();
    }

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

        // 使用第一个字符串作为参考
        String prefix = strs[0];

        // 遍历参考字符串的每个字符
        for (int i = 1; i < strs.length; i++) {
            while (!strs[i].startsWith(prefix)) {
                // 减少前缀长度，直到找到匹配的子串或前缀为空
                prefix = prefix.substring(0, prefix.length() - 1);
                
                // 前缀为空时，表示没有公共前缀，返回 "NO"
                if (prefix.isEmpty()) {
                    return "NO";
                }
            }
        }
        
        return prefix;
    }
}

这段代码首先从用户那里获取输入的字符串数组，然后调用 longestCommonPrefix 函数计算最长公共前缀，并将结果打印出来。longestCommonPrefix 函数中，我们使用了一个 while 循环来动态更新公共前缀的长度，直到找到所有字符串的最长公共前缀或确认不存在公共前缀。