目录

一、题目介绍 

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 用例

二、题目解析

2.1 题目分析

这个题目主要考察以下几个算法和数据结构的知识：

字符串匹配和替换：

在判断两个字符串是否相似时，需要能够快速匹配和替换字符串中的相似字符对。

并查集（Union-Find）算法：

由于相似关系是传递性的，可以用并查集算法来处理这种相似关系，方便快速查找和合并相似字符的集合。

哈希表：

使用哈希表存储相似字符对，方便快速查找和匹配。

2.2 实现思路

读取输入：包括两个专辑名和相似字符对。构建并查集：用并查集来处理相似字符对，构建每个字符的相似集合。字符串归一化：根据并查集，将两个专辑名归一化，即将所有相似字符替换成它们的代表字符。比较归一化后的字符串：判断归一化后的字符串是否相同。如果相同，返回 <code>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] = x

if 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] = rootY

def 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 sys

input = 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）算法来处理字符的相似关系

下期见啦~