题解 | #茉茉的密码#

茉茉的密码

https://www.nowcoder.com/practice/016a87b3015c448da67974d1d731d7ef

题目链接

茉茉的密码

题目描述

给定 $N$ 个仅由小写字母组成的字符串，要求找出这 $N$ 个字符串的一个公共子串。

解题思路

感谢您的指正，注意到本题的数据范围较大（字符串总长度 $\sum |s_i|$ 可达 $10^5$ ），之前的暴力枚举解法在这种情况下会超时。我们需要一个更高效的算法。

题目的关键在于只需要找到任意一个公共子串。这给了我们一个重要的提示：我们可以从最简单的情况入手。

一个公共子串可以很长，也可以很短。最短的子串是长度为 1 的子串，即单个字符。我们可以思考这样一个问题：如果存在一个长度大于 1 的公共子串，例如 "aba"，那么构成这个子串的字符（'a' 和 'b'）是否也一定存在于所有字符串中？答案是肯定的。如果 "aba" 同时出现在字符串 $s_1, s_2, \dots, s_N$ 中，那么字符 'a' 和 'b' 也必然都出现在这些字符串中。

因此，任何一个公共子串中的任意一个字符，本身就是一个长度为 1 的、有效的公共子串。由于题目保证有解，这意味着至少存在一个公共子串。从而，我们推断至少存在一个字符，它在所有 $N$ 个字符串中都出现过。

这样，问题就简化为：找到任意一个在所有 $N$ 个字符串中都出现的字符。

我们可以用以下高效的算法来解决这个问题：

我们维护一个包含26个元素的布尔数组 is_common，is_common[k] 代表字符 'a'+ $k$ 是否是截至目前所有已处理字符串的公共字符。初始时，我们假设所有26个小写字母都是公共的，即将数组所有值设为 true。
接着，我们遍历输入的 $N$ 个字符串。对于每个字符串 $s_i$ ：
我们先创建一个临时的布尔数组 current_exists 来记录 $s_i$ 中出现了哪些字符。
然后，我们用 current_exists 更新 is_common 数组。更新规则是：is_common[k] = is_common[k] AND current_exists[k]。也就是说，只有在之前被认定为公共的、并且在当前字符串 $s_i$ 中也出现的字符，才能继续被认为是公共字符。
遍历完所有 $N$ 个字符串后，is_common 数组中值为 true 的位置所对应的字符，就是所有字符串的公共字符。
根据题意，我们只需输出其中任意一个即可。

这个算法的优势在于，我们只对每个字符处理一次，总的时间复杂度与所有字符串的总长度成正比，能够轻松通过此题。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <string>
#include <numeric>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<bool> is_common(26, true); // 初始时，假设所有字符都是公共的

    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        vector<bool> current_exists(26, false);
        // 记录当前字符串中出现的字符
        for (char c : s) {
            current_exists[c - 'a'] = true;
        }
        // 更新公共字符列表，取交集
        for (int j = 0; j < 26; ++j) {
            if (!current_exists[j]) {
                is_common[j] = false;
            }
        }
    }

    // 找到并输出第一个公共字符
    for (int i = 0; i < 26; ++i) {
        if (is_common[i]) {
            cout << (char)('a' + i) << endl;
            return 0;
        }
    }

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        boolean[] is_common = new boolean[26];
        Arrays.fill(is_common, true); // 初始时，假设所有字符都是公共的

        for (int i = 0; i < n; i++) {
            String s = sc.next();
            boolean[] current_exists = new boolean[26]; // 默认为 false
            // 记录当前字符串中出现的字符
            for (char c : s.toCharArray()) {
                current_exists[c - 'a'] = true;
            }
            // 更新公共字符列表，取交集
            for (int j = 0; j < 26; j++) {
                if (!current_exists[j]) {
                    is_common[j] = false;
                }
            }
        }

        // 找到并输出第一个公共字符
        for (int i = 0; i < 26; i++) {
            if (is_common[i]) {
                System.out.println((char)('a' + i));
                return;
            }
        }
    }
}


def solve():
    n = int(input())
    if n == 0:
        return

    # 初始化公共字符集合为第一个字符串中的字符
    first_s = input()
    common_chars = set(first_s)

    # 与后续字符串的字符集合取交集
    for _ in range(n - 1):
        s = input()
        common_chars.intersection_update(set(s))

    # 题目保证有解，所以集合非空
    # 输出字典序最小的公共字符
    if common_chars:
        print(sorted(list(common_chars))[0])

solve()

算法及复杂度

设字符串数量为 $N$ ，所有字符串的总长度为 $L_{total}$ （即 $L_{total} = \sum_{i=1}^{N} |s_i|$ ）。

算法：字符统计与集合求交。我们通过遍历所有字符串，维护一个只包含26个小写字母的集合（或等效的布尔数组），不断与每个字符串的字符集取交集，最终得到所有字符串的公共字符。
时间复杂度：对于每个字符串 $s_i$ ，我们需要 $\mathcal{O}(|s_i|)$ 的时间来构建它的字符集。对所有字符串进行此操作的总时间为 $\mathcal{O}(\sum |s_i|) = \mathcal{O}(L_{total})$ 。集合求交集的操作因为字母表大小固定为26，所以每次耗时为 $\mathcal{O}(1)$ 。因此，总的时间复杂度为 $\mathcal{O}(L_{total})$ 。
空间复杂度：我们需要存储输入的字符串，在某些实现中可能需要一次性读入，空间为 $\mathcal{O}(L_{total})$ 。算法本身只需要常数大小的额外空间（例如26个布尔值），所以额外空间复杂度为 $\mathcal{O}(1)$ ，总空间复杂度为 $\mathcal{O}(L_{total})$ 。