刷题笔记合集🔗

字符串化繁为简

问题描述

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

数据范围

输入字符串的长度在 之间。

题解

这道题目的核心在于处理等效字符集和字符替换。

解题思路如下：

1. 遍历输入字符串，分别处理括号内和括号外的字符。
2. 对于括号内的字符，将它们加入等效字符集。
3. 对于括号外的字符，将它们保存为结果字符串的一部分。
4. 处理等效字符集，合并有交集的集合。
5. 用等效字符集中字典序最小的字符替换结果字符串中的相应字符。

参考代码

• 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;
        }
    }

    /