解题思路

本题要求找出一组字符串的最长公共前缀。可采用“水平扫描（Horizontal Scanning）”算法： 从第一个字符串作为初始前缀 prefix，依次与后续字符串比较并不断缩短 prefix，直到其成为当前字符串的前缀为止；若某一步缩短到空串，说明不存在公共前缀。

具体做法：

1. 若数组为空，返回空串。

2. 令 prefix = strs[0]。

3. 对于每个后续字符串 s：

   • 当 s 不以 prefix 开头时，持续将 prefix 去掉末尾一个字符（即缩短前缀）。
   • 缩短完成后继续处理下一个字符串。

4. 结束时的 prefix 即为答案。

相关算法说明：

• 水平扫描是经典字符串处理算法，时间复杂度与所有比较过程中被“裁剪”的总字符数成正比，适用于题目所给的字符串数量与长度范围。
• 也可用“排序后比较首尾”或“二分查找+前缀检查”，但在大多数在线评测下，水平扫描实现简单、常数小、易通过。

复杂度分析

• 时间复杂度：O(∑|sᵢ|)。每个字符最多被比较与裁剪一次，总操作数不超过所有字符串长度之和。
• 空间复杂度：O(1)。只使用若干辅助变量，未引入与输入规模相关的额外存储。

代码实现

Python

import sys

def longest_common_prefix(strs):
    if not strs:
        return ""
    prefix = strs[0]
    for s in strs[1:]:
        while not s.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""
    return prefix

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    n = int(data[0])
    strs = data[1:1+n]
    if n == 0:
        print("")
        return
    print(longest_common_prefix(strs))

if __name__ == "__main__":
    main()

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<string> strs(n);
    for (int i = 0; i < n; ++i) cin >> strs[i];

    if (n == 0) { cout << "\n"; return 0; }

    string prefix = strs[0];
    for (int i = 1; i < n && !prefix.empty(); ++i) {
        const string& s = strs[i];
        while (!s.starts_with(prefix)) {
            prefix.pop_back();
            if (prefix.empty()) break;
        }
    }
    cout << prefix << "\n";
    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        Integer nVal = fs.nextInt();
        if (nVal == null) return;
        int n = nVal;
        List<String> strs = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            strs.add(fs.next());
        }
        if (n == 0) {
            System.out.println();
            return;
        }
        String prefix = strs.get(0);
        for (int i = 1; i < n && !prefix.isEmpty(); i++) {
            String s = strs.get(i);
            while (!s.startsWith(prefix)) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) break;
            }
        }
        System.out.println(prefix);
    }

    // 简易读入
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        String next() throws IOException {
            StringBuilder sb = new StringBuilder();
            int c;
            while ((c = read()) != -1 && Character.isWhitespace(c));
            if (c == -1) return null;
            do { sb.append((char)c); } while ((c = read()) != -1 && !Character.isWhitespace(c));
            return sb.toString();
        }
        Integer nextInt() throws IOException {
            String s = next();
            return s == null ? null : Integer.parseInt(s);
        }
    }
}

题目描述

给定一个由小写字母 a-z 组成的字符串数组，求它们的最长公共前缀。若不存在公共前缀，输出空串（即输出一个空行）。

输入格式

• 第一行一个整数 n（n ≥ 0），表示字符串个数。
• 接下来一行或多行包含 n 个仅由小写字母组成的字符串。

输出格式

• 输出一个字符串，为所有输入字符串的最长公共前缀；若不存在则输出空行。

样例1

输入

3
flower flow flight

输出

fl

样例2

输入

3
dog racecar car

输出

（上一行输出为空行，表示空串）