华为OD机试 Python 字符串化繁为简

我会带着你远行 2024-03-08 06:19 85阅读 0赞

### 题目 ###

描述  
给你一串只包含英文字母（无论大写或小写）和小括号的字符。注意，小括号总是成对出现，并且不会互相嵌套。

小括号里的英文字母表示它们之间是等价的。比如在"(ab)“里，‘a’ 和 ‘b’ 是等价的。而在”(bc)"里，‘b’ 和 ‘c’ 是等价的。因此，‘a’、‘b’、和 ‘c’ 三者都是等价的。再加上大写和小写字母本身也是等价的，这些关系会形成一个等价集合。

现在的任务是，你要返回一个新的字符串，保留原字符串中未被小括号包围的字符，并用该字符的等价集合中的最小字符来替代它。如果所有字符都被替代，那么返回"0"。

示例：

输入: “()abd”  
输出: “abd”  
解释: 没有被小括号包围的字符是"abd"，并且没有等价的字符需要替换。

输入: “(abd)demand(fb)()for”  
输出: “aemanaaor”  
解释: ‘a’、‘b’、‘d’ 和 ‘f’ 是等价的。所以用 ‘a’ 这个字符来替代它们。

输入: “()happy(xyz)new(wxy)year(t)”  
输出: “happwnewwear”  
解释: ‘x’、‘y’、‘z’ 和 ‘w’ 是等价的。所以用 ‘w’ 这个字符来替代它们。

### 代码 ###

def extract_tokens(s):
        in_group = False
        content = []
        groups = []
        current_group = []
        for c in s:
            if c == '(':
                in_group = True
                continue
            if c == ')':
                in_group = False
                if current_group:
                    groups.append(set(current_group))
                    current_group = []
                continue
            if in_group:
                current_group.append(c)
            else:
                content.append(c)
        return content, groups
    
    def merge_groups(groups):
        i = 0
        while i < len(groups):
            merged = False
            for j in range(len(groups)):
                if i == j:
                    continue
                if groups[i] & groups[j]:
                    groups[i] = groups[i].union(groups[j])
                    groups.pop(j)
                    merged = True
                    break
            if not merged:
                i += 1
        return groups
    
    def replace_content(content, groups):
        replace_map = {
        }
        for group in groups:
            if group:
                min_char = min(group, key=lambda x: (x.lower(), x))
                for char in group:
                    replace_map[char] = min_char
                    replace_map[char.lower()] = min_char
                    replace_map[char.upper()] = min_char
    
        result = ''.join([replace_map.get(c, c) for c in content])
        return result if result else '0'
    
    def simplify(s):
        content, groups = extract_tokens(s)
        groups = merge_groups(groups)
        return replace_content(content, groups)
    
    input_str = "(abd)demand(fb)()for"
    print(simplify(input_str))