目录
一、题目介绍
1.1 题目描述
1.2 输入描述
1.3 输出描述
1.4 用例
二、题目解析
2.1 题目分析
2.2 实现思路
三、Java实现
3.1 详细代码
3.2 代码解析
四、C#实现
4.1 详细代码
4.2 代码解析
五、Python实现
5.1 完整代码
5.2 代码解析
六、JS实现
6.1 完整代码
6.2 代码解析
七、总结
一、题目介绍
1.1 题目描述
实现一个简易的重复内容识别系统，通过给定的两个内容名称，和相似内容符号，判断两个内容是否相似；如果相似，返回相似内容；如果不相似，返回不相似的内容。
初始化：给出两个字符串，一些相似字符对，如顿号和逗号相似，的和de相似，猪和潴，给出两个字符串的相似判断结果
输入：两条语句，给出是否相似，对于相似的语句，返回True和相似的字符对；对于不相似的内容，则返回第一个内容的不相似信息，方便后续补充
注意：
- 相似关系是 具有 传递性的。例如，如果"顿号"和"逗号"是相似的，"逗号"和"分号"是相似的，则"顿号"和"逗号"是相似的。
- 为了过滤一些无意义的信息，这里***可以匹配任意长度的内容，例如：
给出相似对"(****)",""时，"异世邪君（人气玄幻作家）" 和 "异世邪君" 认为是相似，此时相似符号返回 *** 即可
- 不相似的内容，需要给出不相似的字符串，多处不相似的字符串用空格分隔
1.2 输入描述
- 第一行表示第一张专辑的专辑名，其中 0 < 专辑长度 ≤ 50
- 第二行表示第二张专辑的专辑名，其中 0 < 专辑长度 ≤ 50
- 第三行开始每行为相似的字符串，每行一组，每组字符串不超过10个
- 总共相似字符串行不超过10行
1.3 输出描述
- 第一行返回相似判断的结果，即True或者False
- 第二行开始返回相似/不相似的字符串，每行一组
1.4 用例
| 输入 | 林汉达上下五千年 林汉达上下5千年 五 5 ⑤ 伍 wu |
| 输出 | True 五 5 |
| 说明 | 无 |
| 输入 | 幸福de猪的个人专辑 幸福的猪的个人专辑 得 的 得 de |
| 输出 | True de 的 |
| 说明 | 无 |
| 输入 | 异世邪君(人气玄幻作家) 异世邪君 (***) |
| 输出 | True (***) |
| 说明 | 无 |
| 输入 | 浩然爸爸讲成语 浩然爸爸讲论语 论语 三字经 |
| 输出 | False 成语 论语 |
| 说明 | 无 |
二、题目解析
2.1 题目分析
这个题目主要考察以下几个算法和数据结构的知识：
字符串匹配和替换：
- 在判断两个字符串是否相似时，需要能够快速匹配和替换字符串中的相似字符对。
并查集（Union-Find）算法：
- 由于相似关系是传递性的，可以用并查集算法来处理这种相似关系，方便快速查找和合并相似字符的集合。
哈希表：
- 使用哈希表存储相似字符对，方便快速查找和匹配。
2.2 实现思路
- 读取输入：包括两个专辑名和相似字符对。
- 构建并查集：用并查集来处理相似字符对，构建每个字符的相似集合。
- 字符串归一化：根据并查集，将两个专辑名归一化，即将所有相似字符替换成它们的代表字符。
- 比较归一化后的字符串：判断归一化后的字符串是否相同。如果相同，返回
True和相似字符对；否则，返回False和第一个专辑名中不相似的信息。
三、Java实现
3.1 详细代码
import java.util.*;public class SimilarContentChecker {private static class UnionFind {private Map<String, String> parent;public UnionFind() {parent = new HashMap<>();}public String find(String x) {if (!parent.containsKey(x)) {parent.put(x, x);}if (!x.equals(parent.get(x))) {parent.put(x, find(parent.get(x)));}return parent.get(x);}public void union(String x, String y) {String rootX = find(x);String rootY = find(y);if (!rootX.equals(rootY)) {parent.put(rootX, rootY);}}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取输入String album1 = scanner.nextLine();String album2 = scanner.nextLine();List<String[]> similarPairs = new ArrayList<>();while (scanner.hasNextLine()) {String line = scanner.nextLine();if (line.isEmpty()) break;similarPairs.add(line.split(","));}// 构建并查集UnionFind uf = new UnionFind();for (String[] pair : similarPairs) {for (int i = 0; i < pair.length - 1; i++) {uf.union(pair[i], pair[i + 1]);}}// 字符串归一化String normalizedAlbum1 = normalizeString(album1, uf);String normalizedAlbum2 = normalizeString(album2, uf);// 比较归一化后的字符串if (normalizedAlbum1.equals(normalizedAlbum2)) {System.out.println("True");printSimilarPairs(similarPairs);} else {System.out.println("False");System.out.println(getDifferences(album1, normalizedAlbum1, normalizedAlbum2));}}private static String normalizeString(String s, UnionFind uf) {StringBuilder normalized = new StringBuilder();for (char c : s.toCharArray()) {String str = String.valueOf(c);normalized.append(uf.find(str));}return normalized.toString();}private static void printSimilarPairs(List<String[]> similarPairs) {for (String[] pair : similarPairs) {System.out.println(Arrays.toString(pair));}}private static String getDifferences(String original, String normalized1, String normalized2) {StringBuilder differences = new StringBuilder();for (int i = 0; i < original.length(); i++) {if (normalized1.charAt(i) != normalized2.charAt(i)) {differences.append(original.charAt(i)).append(" ");}}return differences.toString().trim();}
}
3.2 代码解析
详细讲解代码实现步骤
并查集（Union-Find）类：
UnionFind类用于处理字符的相似关系。find方法用于查找字符的根代表，union方法用于合并两个字符的相似集合。读取输入：
- 使用
Scanner读取两个专辑名和相似字符对。- 将相似字符对存储在
similarPairs列表中。构建并查集：
- 对于每一对相似字符对，调用
union方法将它们合并到同一个集合中。字符串归一化：
- 遍历专辑名中的每一个字符，使用
find方法将其归一化为相似集合的代表字符。比较归一化后的字符串：
- 比较归一化后的两个专辑名是否相同。如果相同，输出
True和相似字符对；否则，输出False和第一个专辑名中不相似的信息。
这种方法使用了并查集来高效处理相似关系，并使用哈希表进行字符查找和归一化处理，确保了算法的高效性和准确性。
四、C#实现
4.1 详细代码
using System;
using System.Collections.Generic;public class SimilarContentChecker
{private class UnionFind{private Dictionary<string, string> parent;public UnionFind(){parent = new Dictionary<string, string>();}public string Find(string x){if (!parent.ContainsKey(x)){parent[x] = x;}if (x != parent[x]){parent[x] = Find(parent[x]);}return parent[x];}public void Union(string x, string y){string rootX = Find(x);string rootY = Find(y);if (rootX != rootY){parent[rootX] = rootY;}}}public static void Main(string[] args){string album1 = Console.ReadLine();string album2 = Console.ReadLine();List<string[]> similarPairs = new List<string[]>();string line;while (!string.IsNullOrEmpty(line = Console.ReadLine())){similarPairs.Add(line.Split(','));}UnionFind uf = new UnionFind();foreach (var pair in similarPairs){for (int i = 0; i < pair.Length - 1; i++){uf.Union(pair[i], pair[i + 1]);}}string normalizedAlbum1 = NormalizeString(album1, uf);string normalizedAlbum2 = NormalizeString(album2, uf);if (normalizedAlbum1 == normalizedAlbum2){Console.WriteLine("True");PrintSimilarPairs(similarPairs);}else{Console.WriteLine("False");Console.WriteLine(GetDifferences(album1, normalizedAlbum1, normalizedAlbum2));}}private static string NormalizeString(string s, UnionFind uf){char[] normalized = new char[s.Length];for (int i = 0; i < s.Length; i++){normalized[i] = uf.Find(s[i].ToString())[0];}return new string(normalized);}private static void PrintSimilarPairs(List<string[]> similarPairs){foreach (var pair in similarPairs){Console.WriteLine(string.Join(",", pair));}}private static string GetDifferences(string original, string normalized1, string normalized2){List<char> differences = new List<char>();for (int i = 0; i < original.Length; i++){if (normalized1[i] != normalized2[i]){differences.Add(original[i]);}}return string.Join(" ", differences);}
}
4.2 代码解析
详细讲解代码实现步骤
并查集（Union-Find）类：
UnionFind类用于处理字符的相似关系。Find方法用于查找字符的根代表，Union方法用于合并两个字符的相似集合。读取输入：
- 使用
Console.ReadLine()读取两个专辑名和相似字符对。- 将相似字符对存储在
similarPairs列表中。构建并查集：
- 对于每一对相似字符对，调用
Union方法将它们合并到同一个集合中。字符串归一化：
- 遍历专辑名中的每一个字符，使用
Find方法将其归一化为相似集合的代表字符。比较归一化后的字符串：
- 比较归一化后的两个专辑名是否相同。如果相同，输出
True和相似字符对；否则，输出False和第一个专辑名中不相似的信息。
五、Python实现
5.1 完整代码
class UnionFind:def __init__(self):self.parent = {}def find(self, x):if x not in self.parent:self.parent[x] = xif self.parent[x] != x:self.parent[x] = self.find(self.parent[x])return self.parent[x]def union(self, x, y):rootX = self.find(x)rootY = self.find(y)if rootX != rootY:self.parent[rootX] = rootYdef normalize_string(s, uf):normalized = []for char in s:normalized.append(uf.find(char))return ''.join(normalized)def get_differences(original, normalized1, normalized2):differences = []for o, n1, n2 in zip(original, normalized1, normalized2):if n1 != n2:differences.append(o)return ' '.join(differences)def main():import sysinput = sys.stdin.read().strip().split('\n')album1 = input[0]album2 = input[1]similar_pairs = [line.split(',') for line in input[2:] if line]uf = UnionFind()for pair in similar_pairs:for i in range(len(pair) - 1):uf.union(pair[i], pair[i + 1])normalized_album1 = normalize_string(album1, uf)normalized_album2 = normalize_string(album2, uf)if normalized_album1 == normalized_album2:print("True")for pair in similar_pairs:print(','.join(pair))else:print("False")print(get_differences(album1, normalized_album1, normalized_album2))if __name__ == "__main__":main()
5.2 代码解析
详细讲解代码实现步骤
并查集（Union-Find）类：
UnionFind类用于处理字符的相似关系。find方法用于查找字符的根代表，union方法用于合并两个字符的相似集合。__init__方法初始化一个空的父节点字典parent。find方法使用路径压缩来查找并更新字符的根代表。union方法合并两个字符的相似集合。读取输入：
- 使用
sys.stdin.read()读取输入数据，并将其按行分割成列表。- 前两行是两个专辑名，从第三行开始是相似字符对。
- 将相似字符对存储在
similar_pairs列表中。构建并查集：
- 对于每一对相似字符对，调用
union方法将它们合并到同一个集合中。字符串归一化：
normalize_string函数遍历专辑名中的每一个字符，使用find方法将其归一化为相似集合的代表字符。- 返回归一化后的字符串。
比较归一化后的字符串：
- 比较归一化后的两个专辑名是否相同。如果相同，输出
True和相似字符对；否则，输出False和第一个专辑名中不相似的信息。get_differences函数用于找出原始字符串中不相似的字符，并将它们连接成一个字符串返回。
六、JS实现
6.1 完整代码
class UnionFind {constructor() {this.parent = new Map();}find(x) {if (!this.parent.has(x)) {this.parent.set(x, x);}if (this.parent.get(x) !== x) {this.parent.set(x, this.find(this.parent.get(x)));}return this.parent.get(x);}union(x, y) {let rootX = this.find(x);let rootY = this.find(y);if (rootX !== rootY) {this.parent.set(rootX, rootY);}}
}function normalizeString(s, uf) {return s.split('').map(char => uf.find(char)).join('');
}function getDifferences(original, normalized1, normalized2) {let differences = [];for (let i = 0; i < original.length; i++) {if (normalized1[i] !== normalized2[i]) {differences.push(original[i]);}}return differences.join(' ');
}function main(input) {let lines = input.trim().split('\n');let album1 = lines[0];let album2 = lines[1];let similarPairs = lines.slice(2).map(line => line.split(','));let uf = new UnionFind();for (let pair of similarPairs) {for (let i = 0; i < pair.length - 1; i++) {uf.union(pair[i], pair[i + 1]);}}let normalizedAlbum1 = normalizeString(album1, uf);let normalizedAlbum2 = normalizeString(album2, uf);if (normalizedAlbum1 === normalizedAlbum2) {console.log("True");for (let pair of similarPairs) {console.log(pair.join(','));}} else {console.log("False");console.log(getDifferences(album1, normalizedAlbum1, normalizedAlbum2));}
}// Example usage:
const input = `albumOne
albumTwo
a,b
b,c
c,d`;main(input);
6.2 代码解析
详细讲解代码实现步骤
并查集（Union-Find）类：
UnionFind类用于处理字符的相似关系。find方法用于查找字符的根代表，union方法用于合并两个字符的相似集合。constructor初始化一个空的Map对象parent。find方法使用路径压缩来查找并更新字符的根代表。union方法合并两个字符的相似集合。读取输入：
- 使用
trim().split('\n')读取输入数据，并将其按行分割成列表。- 前两行是两个专辑名，从第三行开始是相似字符对。
- 将相似字符对存储在
similarPairs列表中。构建并查集：
- 对于每一对相似字符对，调用
union方法将它们合并到同一个集合中。字符串归一化：
normalizeString函数遍历专辑名中的每一个字符，使用find方法将其归一化为相似集合的代表字符。- 返回归一化后的字符串。
比较归一化后的字符串：
- 比较归一化后的两个专辑名是否相同。如果相同，输出
True和相似字符对；否则，输出False和第一个专辑名中不相似的信息。getDifferences函数用于找出原始字符串中不相似的字符，并将它们连接成一个字符串返回。
七、总结
这道题目要求我们实现一个系统，用于判断两个字符串是否相似，并且在相似时返回相似的字符对，在不相似时返回第一个字符串中的不相似信息。主要用到了并查集（Union-Find）算法来处理字符的相似关系
下期见啦~