题解

题目描述

给定一个仅由英文字母（'a' ~ 'z'、'A' ~ 'Z'）和左右小括号（'('、')'）组成的字符串。字符串中的小括号是成对出现的，且不会嵌套。小括号内可以包含一个或多个英文字母，也可以为空。当小括号内包含多个字母时，这些字母彼此等效，且等效关系可以在不同的小括号间传递。此外，同一个英文字母的大写和小写字母也互相等效。

需要对输入字符串进行简化，输出一个新的字符串，保留输入字符串中未被小括号包含的字符，并将每个字符替换为其等效字符集合中字典序最小的字符。如果简化后的字符串为空，输出"0"。

思路

1. 建立并查集管理等效关系：

   • 初始化并查集，包含所有大小写英文字母。
   • 将每个字母的小写和大写形式进行合并，使其互相等效。
   • 遍历字符串，找到所有小括号内的字符，将它们在并查集中合并，建立等效关系。

2. 确定每个集合的最小字典序字符：

   • 对于并查集中的每个集合，找到其包含的字符中字典序最小的字符（考虑大小写）。
   • 建立一个映射，将每个字符映射到其集合中的最小字符。

3. 生成输出字符串：

   • 遍历原字符串，筛选出未被小括号包含的字符。
   • 对这些字符应用上述映射，将其替换为对应的最小字符。
   • 如果结果字符串为空，则输出"0"；否则，输出简化后的字符串。

修正要点

• 大小写处理：确保在确定最小字典序字符时，保留字符的原始大小写形式。即，比较字符时应考虑'A' < 'a' < 'B' < 'b'等ASCII顺序。
• 映射关系：在映射时，应将字符映射到其集合中的最小字符，而不是统一转换为小写或大写。

说明

• 等效字符集为('a', 'A', 'b')，其中'A'的ASCII码小于'a'和'b'，因此映射'A'和'a'都映射为'A'。
• 未被括号包含的字符为"abcdefgAC"，其中字符'a'被映射为'A'，其余字符保持不变。
• 输出结果为"AAcdefgAC"，符合要求。

cpp

#include <bits/stdc++.h>
using namespace std;

// 并查集结构
struct UnionFind {
    int parent[256]; // ASCII字符范围
    UnionFind() {
        for(int i=0;i<256;i++) parent[i] = i;
    }
    int find_set(int x){
        return parent[x]==x ? x : parent[x] = find_set(parent[x]);
    }
    void union_set(int x, int y){
        int fx = find_set(x);
        int fy = find_set(y);
        if(fx != fy){
            // 将字典序小的作为父节点
            if(fx < fy) parent[fy] = fx;
            else parent[fx] = fy;
        }
    }
};

int main(){
    string s;
    // 读取整个输入
    getline(cin, s);
    UnionFind uf;
    // 先处理大小写等效
    for(char c='a'; c<='z'; c++){
        uf.union_set(c, toupper(c));
    }
    // 解析字符串，找到所有括号内的字符并建立等效关系
    int n = s.size();
    bool in_parentheses = false;
    vector<char> current;
    for(int i=0;i<n;i++){
        if(s[i] == '('){
            in_parentheses = true;
            current.clear();
        }
        else if(s[i] == ')'){
            // 建立当前括号内字符的等效关系
            if(current.size() >=1 ){
                char first = current[0];
                for(int j=1; j<current.size(); j++) {
                    uf.union_set(first, current[j]);
                }
            }
            in_parentheses = false;
        }
        else{
            if(in_parentheses){
                if( isalpha(s[i]) ){
                    current.push_back(s[i]);
                }
            }
        }
    }
    // 标记哪些字符被括号包含
    vector<bool> is_in_parentheses_flag(n, false);
    in_parentheses = false;
    for(int i=0;i<n;i++){
        if(s[i] == '('){
            in_parentheses = true;
        }
        else if(s[i] == ')'){
            in_parentheses = false;
        }
        else{
            if(in_parentheses){
                is_in_parentheses_flag[i] = true;
            }
        }
    }
    // 找出所有被括号包含的字符并记录
    unordered_set<char> contained_chars;
    for(int i=0;i<n;i++){
        if(is_in_parentheses_flag[i] && isalpha(s[i])){
            contained_chars.insert(s[i]);
        }
    }
    // 为每个字符，找到其最小字典序字符
    unordered_map<char, char> mapping;
    // 使用一个数组记录每个集合的最小字符
    char min_char[256];
    for(int i=0;i<256;i++) min_char[i] = 0;
    for(char c : contained_chars){
        int rep = uf.find_set(c);
        if(min_char[rep] == 0 || c < min_char[rep]){
            min_char[rep] = c;
        }
    }
    // 建立映射
    for(char c : contained_chars){
        int rep = uf.find_set(c);
        if(mapping.find(c) == mapping.end()){
            mapping[c] = min_char[rep];
        }
    }
    // 构建输出字符串
    string output;
    in_parentheses = false;
    for(int i=0;i<n;i++){
        if(s[i] == '('){
            in_parentheses = true;
        }
        else if(s[i] == ')'){
            in_parentheses = false;
        }
        else{
            if(!in_parentheses && isalpha(s[i])){
                char c = s[i];
                if(mapping.find(c) != mapping.end()){
                    output += mapping[c];
                }
                else{
                    output += c;
                }
            }
        }
    }
    if(output.empty()) cout << "0";
    else cout << output;
    return 0;
}

python

class UnionFind:
    def __init__(self):
        self.parent = list(range(256))  # ASCII字符范围

    def find_set(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find_set(self.parent[x])  # 路径压缩
        return self.parent[x]

    def union_set(self, x, y):
        fx = self.find_set(x)
        fy = self.find_set(y)
        if fx != fy:
            # 将字典序小的作为父节点
            if fx < fy:
                self.parent[fy] = fx
            else:
                self.parent[fx] = fy


def simplify_string(s):
    uf = UnionFind()

    # 处理大小写等效
    for c in range(ord('a'), ord('z') + 1):
        uf.union_set(c, ord(chr(c).upper()))  # 修正：将字符c转换为大写后再获取ASCII码

    n = len(s)
    in_parentheses = False
    current = []

    # 解析字符串，找到所有括号内的字符并建立等效关系
    for i in range(n):
        if s[i] == '(':
            in_parentheses = True
            current.clear()
        elif s[i] == ')':
            # 建立当前括号内字符的等效关系
            if len(current) >= 1:
                first = current[0]
                for char in current[1:]:
                    uf.union_set(ord(first), ord(char))
            in_parentheses = False
        else:
            if in_parentheses and s[i].isalpha():
                current.append(s[i])

    # 标记哪些字符被括号包含
    is_in_parentheses_flag = [False] * n
    in_parentheses = False
    for i in range(n):
        if s[i] == '(':
            in_parentheses = True
        elif s[i] == ')':
            in_parentheses = False
        else:
            if in_parentheses:
                is_in_parentheses_flag[i] = True

    # 找出所有被括号包含的字符并记录
    contained_chars = set()
    for i in range(n):
        if is_in_parentheses_flag[i] and s[i].isalpha():
            contained_chars.add(s[i])

    # 为每个字符，找到其最小字典序字符
    mapping = {}
    min_char = [None] * 256

    for c in contained_chars:
        rep = uf.find_set(ord(c))
        if min_char[rep] is None or c < min_char[rep]:
            min_char[rep] = c

    # 建立映射
    for c in contained_chars:
        rep = uf.find_set(ord(c))
        if c not in mapping:
            mapping[c] = min_char[rep]

    # 构建输出字符串
    output = []
    in_parentheses = False
    for i in range(n):
        if s[i] == '(':
            in_parentheses = True
        elif s[i] == ')':
            in_parentheses = False
        else:
            if not in_parentheses and s[i].isalpha():
                output.append(mapping.get(s[i], s[i]))

    # 输出结果
    result = ''.join(output)
    return result if result else "0"


# 测试代码
if __name__ == "__main__":
    input_string = input()
    print(simplify_string(input_string))

java

import java.util.*;

class UnionFind {
    private int[] parent;

    public UnionFind() {
        parent = new int[256]; // ASCII字符范围
        for (int i = 0; i < 256; i++) {
            parent[i] = i;
        }
    }

    public int findSet(int x) {
        if (parent[x] != x) {
            parent[x] = findSet(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    public void unionSet(int x, int y) {
        int fx = findSet(x);
        int fy = findSet(y);
        if (fx != fy) {
            // 将字典序小的作为父节点
            if (fx < fy) {
                parent[fy] = fx;
            } else {
                parent[fx] = fy;
            }
        }
    }
}

public class Main {

    public static String simplifyString(String s) {
        UnionFind uf = new UnionFind();

        // 处理大小写等效
        for (char c = 'a'; c <= 'z'; c++) {
            uf.unionSet(c, Character.toUpperCase(c)); // 将字符c转换为大写后再获取
        }

        int n = s.length();
        boolean inParentheses = false;
        List<Character> current = new ArrayList<>();

        // 解析字符串，找到所有括号内的字符并建立等效关系
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') {
                inParentheses = true;
                current.clear();
            } else if (s.charAt(i) == ')') {
                // 建立当前括号内字符的等效关系
                if (current.size() >= 1) {
                    char first = current.get(0);
                    for (int j = 1; j < current.size(); j++) {
                        uf.unionSet(first, current.get(j));
                    }
                }
                inParentheses = false;
            } else {
                if (inParentheses && Character.isAlphabetic(s.charAt(i))) {
                    current.add(s.charAt(i));
                }
            }
        }

        // 标记哪些字符被括号包含
        boolean[] isInParenthesesFlag = new boolean[n];
        inParentheses = false;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') {
                inParentheses = true;
            } else if (s.charAt(i) == ')') {
                inParentheses = false;
            } else {
                if (inParentheses) {
                    isInParenthesesFlag[i] = true;
                }
            }
        }

        // 找出所有被括号包含的字符并记录
        Set<Character> containedChars = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (isInParenthesesFlag[i] && Character.isAlphabetic(s.charAt(i))) {
                containedChars.add(s.charAt(i));
            }
        }

        // 为每个字符，找到其最小字典序字符
        Map<Character, Character> mapping = new HashMap<>();
        char[] minChar = new char[256];
        Arrays.fill(minChar, '\0');

        for (char c : containedChars) {
            int rep = uf.findSet(c);
            if (minChar[rep] == '\0' || c < minChar[rep]) {
                minChar[rep] = c;
            }
        }

        // 建立映射
        for (char c : containedChars) {
            int rep = uf.findSet(c);
            if (!mapping.containsKey(c)) {
                mapping.put(c, minChar[rep]);
            }
        }

        // 构建输出字符串
        StringBuilder output = new StringBuilder();
        inParentheses = false;
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '(') {
                inParentheses = true;
            } else if (s.charAt(i) == ')') {
                inParentheses = false;
            } else {
                if (!inParentheses && Character.isAlphabetic(s.charAt(i))) {
                    char c = s.charAt(i);
                    output.append(mapping.getOrDefault(c, c));
                }
            }
        }

        // 输出结果
        return output.length() > 0 ? output.toString() : "0";
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String inputString = scanner.nextLine();
        System.out.println(simplifyString(inputString));
    }
}

题目内容

给定一个输入字符串，字符串只可能由英文字母（ '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之间

样例1

输入

()abd

输出

abd

说明

输入字符串里没有被小括号包含的子字符串为"abd"，其中每个字符没有等效字符，输出为"abd"

样例2

输入

(abd)demand(fb)()for

输出

aemanaaor

说明

等效字符集为('a', 'b', 'd', 'f')，输入字符串里没有被小括号包含的子字符串集合为'demandfor"，将其中字符替换为字典序最小的等效字符后输出为："aemanaaor"

样例3

输入

()happy(xyz)new(wxy)year(t)

输出

happwnewwear

说明

等效字符集为(‘x’, 'y', 'z', 'w')，输入字符串里没有被小括号包含的子字符串集合为"happynewyear"，将其中字符替换为字典序最小的等效字符后输出为："happwnewwear"

用例4

输入

()abcdefgAC(a)(Ab)(C)

输出

AAcdefgAC

说明

等效字符集为('a', 'A', 'b')，输入字符里没有被小括号包含的子字符串集合为"abcdefgAC"，将其中字符替换为字典序最小的等效字符后输出为："AAcdefgAC"