题解 | #字符串哈希#

字符串哈希

https://www.nowcoder.com/practice/dadbd37fee7c43f0ae407db11b16b4bf

题目链接

字符串哈希（统计不同字符串）

题目描述

给定 N 个字符串，其中每个字符串仅由数字和大小写字母组成，且区分大小写。请计算这 N 个字符串中不同字符串的个数。

这是一个 ACM 模式 的题目，你需要处理标准输入和输出。

输入描述: 第一行输入整数 N。接下来 N 行，每行输入一个字符串。

输出描述: 输出一个整数，表示不同字符串的数量。

示例: 输入:

6
Hello
World
hello
HELLO
Code
Hello

输出:

解题思路

这道题要求统计不同字符串的数量，是 字符串哈希 的一个经典应用场景。

核心思路是利用 哈希集合 (Hash Set) 这一数据结构。哈希集合的特性是：

自动去重: 集合内部不允许存储重复的元素。
高效查找: 基于哈希表实现，插入和查找操作的平均时间复杂度接近常数。

当我们把字符串存入哈希集合时，集合会自动为每个字符串计算一个哈希值，并根据哈希值将其存放在特定位置。如果之后尝试存入一个相同的字符串，它的哈希值也相同，集合通过检查就能发现元素已存在，从而忽略本次插入操作，实现了去重。

算法步骤:

创建一个空的字符串哈希集合（C++: std::unordered_set<string>，Java: HashSet<String>，Python: set()）。
读取输入的整数 N。
循环 N 次，每次读取一个字符串。
将读取到的字符串插入哈希集合。
所有字符串读取完毕后，集合的大小（size() 或 len()）就是不同字符串的总数。

代码

cpp
java
python

#include <iostream>
#include <string>
#include <unordered_set>

using namespace std;

int main() {
    int n;
    cin >> n;
    unordered_set<string> distinct_strings;
    string s;
    for (int i = 0; i < n; ++i) {
        cin >> s;
        distinct_strings.insert(s);
    }
    cout << distinct_strings.size() << endl;
    return 0;
}

import java.util.Scanner;
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Set<String> distinctStrings = new HashSet<>();
        for (int i = 0; i < n; i++) {
            distinctStrings.add(sc.next());
        }
        System.out.println(distinctStrings.size());
    }
}

n = int(input())
distinct_strings = set()
for _ in range(n):
    s = input()
    distinct_strings.add(s)
print(len(distinct_strings))

算法及复杂度

算法: 哈希集合 (Hash Set)
时间复杂度: $\mathcal{O}(\sum_{i=1}^{N} L_i)$ ，其中 $N$ 是字符串的总数， $L_i$ 是第 $i$ 个字符串的长度。因为将每个字符串插入哈希集合时，需要计算其哈希值，这通常花费与字符串长度成正比的时间。
空间复杂度: $\mathcal{O}(\sum_{j=1}^{M} L_j)$ ，其中 $M$ 是不同字符串的数量， $L_j$ 是第 $j$ 个不同字符串的长度。这是存储所有唯一字符串所需的空间。