字符串化繁为简

题目描述

给定一个输入字符串, 字符串只可能由英文字母 (a-z, A-Z) 和左右小括号 (, ) 组成.

当字符里存在小括号时, 小括号是成对的, 可以有一个或多个小括号对, 小括号对不会嵌套, 小括号对内可以包含1个或多个英文字母, 也可以不包含英文字母.

当小括号对内包含多个英文字母时, 这些字母之间是相互等效的关系, 而且等效关系可以在不同的小括号对之间传递, 即当存在 ‘a’ 和 ‘b’, 等效和存在 ‘b’ 和 ‘c’ 等效时, ‘a’ 和 ‘c’ 也等效, 另外, 同一个英文字母的大写字母和小写字母也相互等效, 即使它们分布在不同的括号对里.

需要对这个输入字符串做简化, 输出一个新的字符串, 输出字符串里只需保留输入字符串里的没有被小括号对包含的字符, 按照输入字符串里的字符顺序, 并将每个字符替换为在小括号对里包含的且字典序最小的等效字符.

如果简化后的字符串为空, 请输出为"0".

示例:

输入字符串为 never(dont)give(run)up(f)(), 初始等效字符集合为 , o, n, t, r, u, n, 由于等效关系可以传递, 因此最终等效字符集合为 d, o, n, t, r, u, 将输入字符串里的剩余部分按字典序最小的等效字符替换后得到 devedgivedp.

输入描述

input_string

输入为1行, 代表输入字符串.

备注: 输入字符串的长度在1~100000之间.

输出描述

output_string

输出为1行, 代表输出字符串.

示例1

输入:

()abd

输出:

abd

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

示例2

输入:

(abd)demand(fb)()for

输出:

aemanaaor

示例3

输入:

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

输出:

happwnewwear

说明: 等效字符集为 x, y, z, w, 输入字符串里没有被小括号包含的子字符串集合为 happynewyear, 将其中字符替换为字典序最小的等效字符后输出为 happwnewwear.

示例4

输入:

never(dont)give(run)up(f)()

输出:

devedgivedp

说明:

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

题解

Python

# 简单的字符串替换
def main():
    # 读取输入
    s = input()
    assert 1 < len(s) < 100000

    # 然后解析所有的括号, 并读取里面的所有字符, 并对它们进行排序, 做成一个替换表
    # 然后将它们从字符串s中移除
    # 最后使用替换表将字符串s中的字符替换成最小序的字符
    raw_chars = []
    tab_chars = []
    found_bracket = False
    for char in s:
        if char == "(":
            found_bracket = True
        elif char == ")":
            found_bracket = False
        elif found_bracket:
            tab_chars.append(char)
        else:
            raw_chars.append(char)

    raw_str = "".join(raw_chars)

    # 对替换表进行排序, 可以找出最小序的字母
    tab_chars.sort()
    if len(tab_chars) > 1:
        first_char = tab_chars[0]
        tab_dict = dict((char, first_char) for char in tab_chars[1:])
        if len(tab_dict) > 1:
            raw_str = raw_str.translate(str.maketrans(tab_dict))

    print(raw_str)

if __name__ == "__main__":
    main()