【华为OD-E卷 - 字符串化繁为简 100分（python、java、c++、js、c）】
题目
给定一个输入字符串，字符串只可能由英文字母（ ‘a’ ~ ‘z’、‘A’ ~ ‘Z’ ）和左右小括号（ ‘(’、‘)’ ）组成。
当字符里存在小括号时，小括号是成对的，可以有一个或多个小括号对，小括号对不会嵌套，小括号对内可以包含1个或多个英文字母，也可以不包含英文字母。
当小括号对内包含多个英文字母时，这些字母之间是相互等效的关系，而且等效关系可以在不同的小括号对之间传递，即当存在 ‘a’ 和 ‘b’ 等效和存在 ‘b’ 和 ‘c’ 等效时，‘a’ 和 ‘c’ 也等效，另外，同一个英文字母的大写字母和小写字母也相互等效（即使它们分布在不同的括号对里）
需要对这个输入字符串做简化，输出一个新的字符串，输出字符串里只需保留输入字符串里的没有被小括号对包含的字符（按照输入字符串里的字符顺序），并将每个字符替换为在小括号对里包含的且字典序最小的等效字符。
如果简化后的字符串为空，请输出为"0"。
示例 : 输入字符串为"never(dont)give(run)up(f)()“，初始等效字符集合为(‘d’, ‘o’, ‘n’, ‘t’)、(‘r’, ‘u’, ‘n’)，由于等效关系可以传递，因此最终等效字符集合为(‘d’, ‘o’, ‘n’, ‘t’, ‘r’, ‘u’)，将输入字符串里的剩余部分按字典序最小的等效字符替换后得到"devedgivedp”
输入描述
- input_string
输入为1行，代表输入字符串
输出描述
- output_string
输出为1行，代表输出字符串
备注
- 输入字符串的长度在1~100000之间
用例
用例一：
输入：
()abd
- 1
输出：
abd
- 1
用例二：
输入：
(abd)demand(fb)()for
- 1
输出：
aemanaaor
- 1
用例三：
输入：
()happy(xyz)new(wxy)year(t)
- 1
输出：
happwnewwear
- 1
用例四：
输入：
()abcdefgAC(a)(Ab)(C)
- 1
输出：
AAcdefgAC
- 1
说明 等效字符集为(‘a’, ‘A’, ‘b’)，输入字符里没有被小括号包含的子字符串集合为"abcdefgAC"，将其中字符替换为字典序最小的等效字符后输出为：“AAcdefgAC”
python解法
- 解题思路：
- 问题描述：
输入一个包含普通字符和括号的字符串，括号内的字符代表一组等价字符。例如，输入 (ab)c(d)e 表示：
‘a’ 和 ‘b’ 等价；
‘d’ 等价于自身；
外部字符 ‘c’ 和 ‘e’ 与括号中的字符没有关系。
任务是将字符串中所有等价字符替换为其字典序最小的字符，并输出替换后的字符串。
如果输入中没有普通字符，则返回 0。
实现步骤：
解析输入：
遍历字符串，将括号中的字符分组存入等价集合 equivalent_sets。
将不在括号内的字符存入 body_chars。
处理等价集合：
合并等价集合：如果两个集合中有字符相同或字符大小写等价（如 ‘a’ 和 ‘A’），则将它们合并为一个集合。
字符替换：
遍历等价集合，将集合中的字符替换为集合中字典序最小的字符。
遍历 body_chars，根据等价集合中的替换规则更新其值。
输出结果：
将处理后的字符拼接为字符串并返回。
如果没有普通字符，返回 0。
核心逻辑：
合并等价集合：两个集合是否合并取决于它们是否包含相同的字符或大小写等价字符。
替换规则：对于每个等价集合，用集合中字典序最小的字符替换所有等价字符。
时间复杂度：
解析输入：O(n)，其中 n 为字符串长度。
合并集合：最坏情况下 O(m² * k)，其中 m 是等价集合的数量，k 是单个集合的最大长度。
替换字符：O(n)。
class CharacterProcessor:
def __init__(self):
self.equivalent_sets = [] # 用于存储等价字符集合
self.body_chars = [] # 用于存储不在括号中的普通字符
def process_input(self, s):
"""
解析输入字符串，将括号中的字符分组为等价集合，将普通字符存入 body_chars。
"""
is_open = False # 标记是否在括号内
for c in s:
if c == '(':
# 遇到左括号，开启新的等价集合
is_open = True
self.equivalent_sets.append(set())
elif c == ')':
# 遇到右括号，关闭当前等价集合
is_open = False
# 如果当前集合为空，移除它
if len(self.equivalent_sets[-1]) == 0:
self.equivalent_sets.pop()
else:
if not is_open:
# 如果不在括号内，将字符添加到 body_chars
self.body_chars.append(c)
else:
# 如果在括号内，将字符添加到当前等价集合
self.equivalent_sets[-1].add(c)
def can_combine(self, set1, set2):
"""
检查两个集合是否可以合并（有共同字符或字符大小写等价）。
"""
for c in range(97, 123): # 检查 'a' 到 'z'
lc = chr(c) # 小写字符
uc = chr(c - 32) # 对应的大写字符
if (lc in set1 or uc in set1) and (lc in set2 or uc in set2):
return True
return False
def merge_equivalents(self):
"""
合并等价集合，直到无法再合并。
"""
while self._perform_merge():
pass
def _perform_merge(self):
"""
执行一次等价集合的合并操作。
"""
for i in range(len(self.equivalent_sets)):
for j in range(i + 1, len(self.equivalent_sets)):
# 如果两个集合可以合并，则合并它们
if self.can_combine(self.equivalent_sets[i], self.equivalent_sets[j]):
tmp = list(self.equivalent_sets[i])
tmp.extend(self.equivalent_sets[j])
self.equivalent_sets[i] = set(tmp)
self.equivalent_sets.pop(j)
return True
return False
def replace_with_min_characters(self):
"""
使用等价集合中的最小字符替换所有等价字符。
"""
for eq in self.equivalent_sets:
tmp = list(eq)
tmp.sort() # 对集合排序
min_char = tmp[0] # 获取字典序最小的字符
# 替换 body_chars 中的字符
for i in range(len(self.body_chars)):
if self.body_chars[i] in eq:
self.body_chars[i] = min_char
def get_result(self):
"""
返回处理后的字符串结果。如果没有普通字符，返回 "0"。
"""
return "".join(self.body_chars) if self.body_chars else "0"
def getResult(s):
"""
主函数：解析字符串，处理等价关系并返回结果。
"""
processor = CharacterProcessor()
processor.process_input(s) # 解析输入
processor.merge_equivalents() # 合并等价集合
processor.replace_with_min_characters() # 替换字符
return processor.get_result()
if __name__ == "__main__":
input_string = input() # 读取输入字符串
print(getResult(input_string)) # 输出结果
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
java解法
- 解题思路
- 问题描述：
输入一个字符串，包含括号中的字符等价关系。
括号中的字符表示等价，多个括号的关系通过联合并查集（Union-Find）进行合并。
外部的字符按原顺序保留，最终将所有字符替换为它们等价类中的字典序最小字符。
如果没有外部字符，返回 “0”。
解决方法：
Union-Find 解决等价关系：
使用并查集（Union-Find）结构存储字符的等价关系。
每个字符初始化为一个独立的集合，表示自身等价。
遇到括号内的字符时，合并这些字符的集合。
字符映射：
使用一个大小为 52 的并查集（a-z 和 A-Z 分别映射到 0-25 和 26-51）。
字符通过索引映射到并查集中的位置。
结果替换：
遍历字符串，将每个字符替换为它等价类中的字典序最小字符。
输入输出：
输入：
一个字符串，包含普通字符和括号中的等价关系。
输出：
字符串中所有字符替换为等价类中最小字符后的结果；
如果没有普通字符，返回 “0”。
核心逻辑：
Union-Find：
每个字符初始化为独立集合。
使用 union 合并等价字符集合。
使用 find 查找字符所属集合，并获取集合中字典序最小的字符。
字符串处理：
遍历字符串：
括号内的字符加入等价集合。
普通字符直接加入结果。
替换普通字符为等价类中的最小字符
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取输入字符串
String input = scanner.nextLine();
// 调用 simplifyString 方法并打印结果
System.out.println(simplifyString(input));
}
/**
* 解析字符串并处理等价关系，返回简化后的字符串
* @param s 输入字符串
* @return 简化后的字符串，如果没有普通字符返回 "0"
*/
public static String simplifyString(String s) {
// 初始化 Union-Find，支持 52 个字符（a-z 和 A-Z）
UnionFind uf = new UnionFind(52);
StringBuilder result = new StringBuilder(); // 存储外部字符
boolean insideBracket = false; // 标记是否在括号内
Set<Character> seenChars = new HashSet<>(); // 存储当前括号中的字符
// 遍历输入字符串
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
// 遇到左括号，进入括号模式
insideBracket = true;
} else if (c == ')') {
// 遇到右括号，退出括号模式，并清空 seenChars
insideBracket = false;
seenChars.clear();
} else if (insideBracket) {
// 处理括号内的字符，将其加入等价集合
seenChars.add(c);
for (char seen : seenChars) {
uf.union(seen, c); // 合并等价关系
}
} else {
// 普通字符，直接加入结果
result.append(c);
}
}
// 替换普通字符为等价类中的最小字符
char[] finalResult = result.toString().toCharArray();
for (int i = 0; i < finalResult.length; i++) {
finalResult[i] = uf.findMinEquivalent(finalResult[i]);
}
// 如果结果为空，返回 "0"
String simplified = new String(finalResult);
return simplified.isEmpty() ? "0" : simplified;
}
}
/**
* Union-Find 数据结构，用于存储字符的等价关系
*/
class UnionFind {
private int[] parent; // 存储每个节点的父节点
private char[] minEquivalent; // 存储每个集合中的字典序最小字符
public UnionFind(int size) {
// 初始化并查集
parent = new int[size];
minEquivalent = new char[size];
for (int i = 0; i < size; i++) {
parent[i] = i; // 每个节点初始化为自己的父节点
// 初始化最小字符为对应字符
minEquivalent[i] = (char) (i < 26 ? 'a' + i : 'A' + (i - 26));
}
}
/**
* 查找节点的根节点，并路径压缩
* @param x 节点索引
* @return 根节点索引
*/
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
minEquivalent[x] = minEquivalent[parent[x]]; // 更新最小字符
}
return parent[x];
}
/**
* 合并两个字符的等价关系
* @param a 字符 a
* @param b 字符 b
*/
public void union(char a, char b) {
int rootA = find(charToIndex(a)); // 查找 a 的根节点
int rootB = find(charToIndex(b)); // 查找 b 的根节点
if (rootA != rootB) {
// 将字典序较小的字符作为父节点
if (minEquivalent[rootA] < minEquivalent[rootB]) {
parent[rootB] = rootA;
minEquivalent[rootA] = (char) Math.min(minEquivalent[rootA], minEquivalent[rootB]);
} else {
parent[rootA] = rootB;
minEquivalent[rootB] = (char) Math.min(minEquivalent[rootA], minEquivalent[rootB]);
}
}
}
/**
* 查找字符的等价类中的最小字符
* @param c 输入字符
* @return 字典序最小的等价字符
*/
public char findMinEquivalent(char c) {
return minEquivalent[find(charToIndex(c))];
}
/**
* 将字符映射到索引位置
* @param c 输入字符
* @return 索引位置
*/
private int charToIndex(char c) {
return c >= 'a' ? c - 'a' : c - 'A' + 26;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
C++解法
- 解题思路
更新中
- 1
C解法
更新中
- 1
JS解法
输入字符串包含普通字符和括号中的字符等价关系。
括号中的字符等价（如 (ab) 表示 a 和 b 是等价的）。
字符串中的每个字符需替换为其等价类中字典序最小的字符。
如果输入中没有普通字符，输出 “0”。
解决方案：
使用并查集（Union-Find）存储字符的等价关系。
每个字符初始化为独立集合，通过 union 操作合并等价字符。
遍历普通字符并通过并查集找到它们的等价类中的字典序最小字符。
拼接替换后的字符并返回结果。
实现步骤：
初始化并查集：
使用对象 parent 存储字符的父节点。
find 方法：找到字符的根节点，并路径压缩。
union 方法：将两个字符的根节点合并为一个。
解析字符串：
遍历字符串：
遇到 ( 开始记录括号内字符。
遇到 ) 合并括号内字符的等价关系。
普通字符直接加入结果数组。
替换字符：
遍历结果数组，将每个字符替换为并查集中的字典序最小字符。
输出结果：
如果结果数组为空，返回 “0”。
时间复杂度：
解析字符串：O(n)，其中 n 是字符串长度。
并查集操作：近似 O(1)（由于路径压缩和按秩合并）。
字符替换：O(n)
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
// 主输入处理逻辑
rl.on("line", (line) => {
console.log(simplifyString(line)); // 调用 simplifyString 方法并输出结果
});
/**
* 简化字符串，将等价字符替换为最小字符
* @param {string} s 输入字符串
* @returns {string} 处理后的字符串，如果没有普通字符返回 "0"
*/
function simplifyString(s) {
const parent = {}; // 并查集 parent，用于存储字符的父节点
/**
* 并查集 find 方法：找到字符的根节点，并路径压缩
* @param {char} x 字符
* @returns {char} 根节点字符
*/
function find(x) {
if (parent[x] === undefined) {
parent[x] = x; // 如果字符未初始化，初始化为自身
}
if (parent[x] !== x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
/**
* 并查集 union 方法：合并两个字符的集合
* @param {char} x 第一个字符
* @param {char} y 第二个字符
*/
function union(x, y) {
const rootX = find(x); // 找到 x 的根节点
const rootY = find(y); // 找到 y 的根节点
if (rootX !== rootY) {
// 按字典序合并集合，较小的字符作为父节点
if (rootX < rootY) parent[rootY] = rootX;
else parent[rootX] = rootY;
}
}
const cArr = []; // 存储普通字符
let isOpen = false; // 标记是否在括号内
let eqSet = []; // 临时存储当前括号内的字符
// 遍历输入字符串
for (let i = 0; i < s.length; i++) {
const c = s[i];
if (c === '(') {
// 遇到左括号，开始记录括号内字符
isOpen = true;
eqSet = []; // 初始化当前括号内字符集合
} else if (c === ')') {
// 遇到右括号，结束记录并合并等价集合
isOpen = false;
for (let ch1 of eqSet) {
for (let ch2 of eqSet) {
union(ch1.toLowerCase(), ch2.toLowerCase()); // 合并等价关系
}
}
} else {
if (!isOpen) {
// 如果不在括号内，直接加入普通字符数组
cArr.push(c);
} else {
// 如果在括号内，加入临时集合 eqSet
eqSet.push(c);
}
}
}
// 替换普通字符为并查集中等价类中的最小字符
const ans = cArr.map(c => find(c.toLowerCase())).join("");
// 如果结果为空，返回 "0"
return ans.length === 0 ? "0" : ans;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
评论记录：
回复评论：