E卷-字符串化繁为简(200分)
字符串化繁为简
问题描述
给定一个输入字符串，字符串只可能由英文字母（'a' ~ 'z'、'A' ~ 'Z'）和左右小括号（'('、')'）组成。
当字符里存在小括号时，小括号是成对的，可以有一个或多个小括号对，小括号对不会嵌套，小括号对内可以包含 1 个或多个英文字母，也可以不包含英文字母。
当小括号对内包含多个英文字母时，这些字母之间是相互等效的关系，而且等效关系可以在不同的小括号对之间传递，即当存在 'a' 和 'b' 等效和存在 'b' 和 'c' 等效时，'a' 和 'c' 也等效，另外，同一个英文字母的大写字母和小写字母也相互等效（即使它们分布在不同的括号对里）。
需要对这个输入字符串做简化，输出一个新的字符串，输出字符串里只需保留输入字符串里的没有被小括号对包含的字符（按照输入字符串里的字符顺序），并将每个字符替换为在小括号对里包含的且字典序最小的等效字符。
如果简化后的字符串为空，请输出为"0"。
输入格式
输入为 1 行，代表输入字符串 。
输出格式
输出为 1 行，代表输出字符串 。
样例输入
()abd
样例输出
abd
样例解释
输入字符串里没有被小括号包含的子字符串为"abd"，其中每个字符没有等效字符，输出为"abd"。
样例输入
(abd)demand(fb)()for
样例输出
aemanaaor
样例解释
等效字符集为('a', 'b', 'd', 'f')，输入字符串里没有被小括号包含的子字符串集合为"demandfor"，将其中字符替换为字典序最小的等效字符后输出为："aemanaaor"。
样例输入
()happy(xyz)new(wxy)year(t)
样例输出
happwnewwear
样例解释
等效字符集为('x', 'y', 'z', 'w')，输入字符串里没有被小括号包含的子字符串集合为"happynewyear"，将其中字符替换为字典序最小的等效字符后输出为："happwnewwear"。
样例输入
()abcdefgAC(a)(Ab)(C)
样例输出
AAcdefgAC
样例解释
等效字符集为('a', 'A', 'b')，输入字符里没有被小括号包含的子字符串集合为"abcdefgAC"，将其中字符替换为字典序最小的等效字符后输出为："AAcdefgAC"。
数据范围
输入字符串的长度在 之间。
题解
这道题目的核心在于处理等效字符集和字符替换。
解题思路如下：
- 遍历输入字符串，分别处理括号内和括号外的字符。
- 对于括号内的字符，将它们加入等效字符集。
- 对于括号外的字符，将它们保存为结果字符串的一部分。
- 处理等效字符集，合并有交集的集合。
- 用等效字符集中字典序最小的字符替换结果字符串中的相应字符。
参考代码
- Python
import sys
def input():
return sys.stdin.readline().strip()
def process_equivalence_sets(eq_sets, result):
"""
处理等效字符集并替换结果字符串中的字符
Args:
eq_sets (list): 等效字符集列表
result (list): 需要处理的字符列表
Returns:
None (直接修改 result 列表)
"""
modified = True
while modified:
modified = False
i = 0
while i < len(eq_sets):
j = i + 1
while j < len(eq_sets):
# 检查两个集合是否有交集
if any(c.lower() in eq_sets[j] or c.upper() in eq_sets[j] for c in eq_sets[i]):
# 合并两个集合
eq_sets[i].update(eq_sets[j])
eq_sets.pop(j)
modified = True
else:
j += 1
if modified:
break
i += 1
# 用字典序最小的等效字符替换结果中的字符
for eq_set in eq_sets:
min_char = min(eq_set)
for i, c in enumerate(result):
if c in eq_set:
result[i] = min_char
def main():
"""
主函数，处理输入并输出结果
"""
s = input()
result = []
eq_sets = []
in_parentheses = False
# 遍历输入字符串
for c in s:
if c == '(':
in_parentheses = True
eq_sets.append(set())
elif c == ')':
in_parentheses = False
if not eq_sets[-1]:
eq_sets.pop()
elif in_parentheses:
eq_sets[-1].add(c)
else:
result.append(c)
# 处理等效字符集并替换结果中的字符
process_equivalence_sets(eq_sets, result)
# 输出结果
final_result = ''.join(result) if result else '0'
print(final_result)
if __name__ == "__main__":
main()
- C
待跟新
- Javascript
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
// 处理等价集合并替换字符
function procEq(sets, res) {
let chg = true;
while (chg) {
chg = false;
for (let i = 0; i < sets.length; i++) {
for (let j = i + 1; j < sets.length; j++) {
// 检查两个集合是否有交集
if ([...sets[i]].some(c =>
sets[j].has(c.toLowerCase()) || sets[j].has(c.toUpperCase()))) {
// 合并集合
sets[i] = new Set([...sets[i], ...sets[j]]);
sets.splice(j, 1);
chg = true;
break;
}
}
if (chg) break;
}
}
// 用每个集合中字典序最小的字符替换结果中的字符
for (let set of sets) {
let mn = [...set].sort()[0];
for (let i = 0; i < res.length; i++) {
if (set.has(res[i])) {
res[i] = mn;
}
}
}
}
rl.question('', (s) => {
let res = [];
let sets = [];
let inPar = false;
// 遍历输入字符串
for (let c of s) {
if (c === '(') {
inPar = true;
sets.push(new Set());
} else if (c === ')') {
inPar = false;
if (sets[sets.length - 1].size === 0) {
sets.pop();
}
} else if (inPar) {
sets[sets.length - 1].add(c);
} else {
res.push(c);
}
}
// 处理等价集合并替换字符
procEq(sets, res);
// 输出结果
console.log(res.length > 0 ? res.join('') : '0');
rl.close();
});
- Java
import java.util.*;
import java.io.*;
public class Main {
// 快速读取类，用于高效输入
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
}
// 处理等价集合并替换字符
static void procEq(List<Set<Character>> sets, StringBuilder res) {
boolean chg = true;
while (chg) {
chg = false;
for (int i = 0; i < sets.size(); i++) {
for (int j = i + 1; j < sets.size(); j++) {
// 检查两个集合是否有交集
if (hasIntersection(sets.get(i), sets.get(j))) {
// 合并集合
sets.get(i).addAll(sets.get(j));
sets.remove(j);
chg = true;
break;
}
}
if (chg) break;
}
}
// 用每个集合中字典序最小的字符替换结果中的字符
for (Set<Character> st : sets) {
char mn = Collections.min(st);
for (int i = 0; i < res.length(); i++) {
if (st.contains(res.charAt(i))) {
res.setCharAt(i, mn);
}
}
}
}
// 检查两个集合是否有交集
static boolean hasIntersection(Set<Character> set1, Set<Character> set2) {
for (char c : set1) {
if (set2.contains(Character.toLowerCase(c)) || set2.contains(Character.toUpperCase(c))) {
return true;
}
}
return false;
}
public static void main(String[] args) {
FastReader fr = new FastReader();
String s = fr.next();
StringBuilder res = new StringBuilder();
List<Set<Character>> sets = new ArrayList<>();
boolean inPar = false;
// 遍历输入字符串
for (char c : s.toCharArray()) {
if (c == '(') {
inPar = true;
sets.add(new HashSet<>());
} else if (c == ')') {
inPar = false;
if (sets.get(sets.size() - 1).isEmpty()) {
sets.remove(sets.size() - 1);
}
} else if (inPar) {
sets.get(sets.size() - 1).add(c);
} else {
res.append(c);
}
}
// 处理等价集合并替换字符
procEq(sets, res);
// 输出结果
System.out.println(res.length() > 0 ? res.toString() : "0");
}
}
- Cpp
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
using namespace std;
// 处理等价集合并替换字符
void procEq(vector<set<char>>& sets, string& res) {
bool chg = true;
while (chg) {
chg = false;
for (auto it1 = sets.begin(); it1 != sets.end(); ++it1) {
for (auto it2 = next(it1); it2 != sets.end();) {
// 检查两个集合是否有交集
if (any_of(it1->begin(), it1->end(), [&](char c) {
return it2->count(tolower(c)) || it2->count(toupper(c));
})) {
// 合并集合
it1->insert(it2->begin(), it2->end());
it2 = sets.erase(it2);
chg = true;
break;
} else {
++it2;
}
}
if (chg) break;
}
}
// 用每个集合中字典序最小的字符替换结果中的字符
for (const auto& st : sets) {
char mn = *min_element(st.begin(), st.end());
for (char& c : res) {
if (st.count(c)) c = mn;
}
}
}
int main() {
string s, res;
vector<set<char>> sets;
bool inPar = false;
cin >> s;
// 遍历输入字符串
for (char c : s) {
if (c == '(') {
inPar = true;
sets.emplace_back();
} else if (c == ')') {
inPar = false;
if (sets.back().empty()) sets.pop_back();
} else if (inPar) {
sets.back().insert(c);
} else {
res += c;
}
}
// 处理等价集合并替换字符
procEq(sets, res);
// 输出结果
cout << (res.empty() ? "0" : res) << endl;
return 0;
}
OD刷题笔记 文章被收录于专栏
本专栏收集并整理了一些刷题笔记
多益网络一面71人在聊