#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define PII pair<int, int>
#define PDI pair<double, int>
#define all(x) x.begin(), x.end()
#define quickcin() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1e3 + 10, MINRAND = 0, MAXRAND = 1e9;

mt19937 rnd1(time(0));
mt19937_64 rnd2(time(0));
uniform_int_distribution<> int_mt(MINRAND, MAXRAND);
uniform_real_distribution<> double_mt(MINRAND, MAXRAND);
bool cmp(string a, string b)
{
    return a + b < b + a;
}
string dfs(string s)
{
    if (!s.size())
        return "";
    vector<string> tmp, subs;
    int cnt = 0;
    string res = "";
    for (auto i : s)
    {
        if (i == '(')
            cnt++;
        else
            cnt--;
        res += i;
        if (!cnt)
        {
            subs.pb(res);
            res = "";
        }
    }
    if (subs.size() == 1)
    {
        tmp.pb('(' + dfs(subs[0].substr(1, subs[0].size() - 2)) + ')');
    }
    else
    {
        for (auto s2 : subs)
        {
            tmp.pb(dfs(s2));
        }
    }
    sort(all(tmp), cmp);
    string ans = "";
    for (auto i : tmp)
        ans += i;
    return ans;
}
void solve()
{
    string s;
    cin >> s;
    cout << dfs(s);
}

signed main()
{
    quickcin();
    int _ = 1;
    // cin >> _;
    while (_--)
    {
        solve();
    }
}

题目描述

给定一个合法的括号序列，要求通过对其进行若干次（或不进行）的相邻合法括号子序列的交换，得到字典序最大的括号序列。每个合法的括号序列由左右括号组成，并且是有效的括号匹配。

解题思路

这道题的核心在于递归拆分括号子序列，然后对子序列进行字典序排序。我们可以将括号表达式看作是树状的结构，递归处理括号内部的子结构并保证排序合并后的结果是字典序最大的表达式。

思路步骤

1. 递归拆分括号序列：

   • 对于给定的括号表达式，我们先从左到右遍历，使用一个计数器 cnt 来跟踪当前括号的匹配状态。当计数器归零时，说明我们找到了一个完整的合法括号序列（即一对匹配的 ()）。
   • 然后我们可以将这个合法括号序列作为一个独立的子结构进行递归处理。

2. 递归处理每个子序列：

   • 对于每个合法括号序列，可以递归调用相同的函数进行处理。对于单一的括号序列（如 (())），可以去掉外层的括号，递归处理里面的内容；对于多个子括号序列（如 ()()），可以分别递归处理。

3. 字典序排序：

   • 当多个子括号序列被递归处理后，按照 a + b 和 b + a 的字典序进行比较，来决定两个子序列的拼接顺序。这种拼接保证了最终的括号表达式的字典序最大。

   • 例如，如果两个子序列 a 和 b，如果 a + b 的字典序大于 b + a，那么 a 应该排在 b 的前面。

   • Q:为什么这么排序？A:见LeetCode 179.最大数

4. 合并排序后的结果：

   • 在排序完成后，将这些子序列按顺序拼接起来，形成当前层次的括号表达式，返回给上一层递归。

代码

java

import java.util.*;

public class Main {
    // 自定义比较器，用来比较两个字符串拼接的字典序
    public static int compare(String a, String b) {
        if ((a + b).compareTo(b + a) > 0) {
            return 1;
        } else if ((a + b).compareTo(b + a) < 0) {
            return -1;
        } else {
            return 0;
        }
    }

    // 深度优先搜索函数，递归处理括号表达式
    public static String dfs(String s) {
        if (s.length() == 0) {
            return "";
        }
        
        List<String> part = new ArrayList<>();
        StringBuilder now = new StringBuilder();
        int cnt = 0;
        
        // 分割括号表达式，按完整的括号对划分
        for (char c : s.toCharArray()) {
            if (c == '(') {
                cnt++;
            } else {
                cnt--;
            }
            now.append(c);
            if (cnt == 0) { // 找到一个完整的括号对
                part.add(now.toString());
                now = new StringBuilder();
            }
        }

        List<String> subRes = new ArrayList<>();
        
        if (part.size() == 1) {
            // 如果只有一个完整的括号对，递归处理去掉最外层括号后的子表达式
            subRes.add("(" + dfs(part.get(0).substring(1, part.get(0).length() - 1)) + ")");
        } else {
            // 递归处理多个括号对
            for (String p : part) {
                subRes.add(dfs(p));
            }
        }

        // 排序子表达式，使得字典序最大
        Collections.sort(subRes, (a, b) -> compare(a, b));

        // 返回拼接后的结果
        return String.join("", subRes);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next(); // 输入括号字符串
        System.out.println(dfs(s)); // 输出处理后的结果
    }
}

python

from functools import cmp_to_key

# 读取输入的括号字符串
s = input()

# 自定义比较函数，比较 a 和 b 的拼接顺序，决定字典序的顺序
# 如果 a + b > b + a，返回 1，表示 a 应该排在 b 的后面
# 如果 a + b < b + a，返回 -1，表示 a 应该排在 b 的前面
# 否则返回 0 表示相等
def compare(a, b):
    if a + b > b + a:
        return 1
    elif a + b < b + a:
        return -1
    return 0

# 深度优先搜索 (DFS) 函数，用来递归处理括号表达式
def dfs(s):
    # 如果当前字符串为空，直接返回空字符串
    if len(s) == 0:
        return ""

    part = []  # 用于存储当前括号层的所有子括号表达式
    now = ""   # 临时变量，记录当前子表达式
    cnt = 0    # 计数器，判断当前括号是否匹配

    # 遍历字符串中的每个字符
    for c in s:
        if c == '(':  # 遇到左括号时，计数器加 1
            cnt += 1 
        else:  # 遇到右括号时，计数器减 1
            cnt -= 1
        now += c  # 将当前字符加入到子表达式中

        # 当计数器为 0 时，说明当前子表达式是一个完整的括号对
        if cnt == 0:
            part.append(now)  # 将完整的子表达式存入 part 列表中
            now = ""  # 重置 now，开始处理下一个子表达式

    sub_res = []  # 存储处理后的子表达式结果

    # 如果 part 只有一个完整的括号对
    if len(part) == 1:
        # 递归处理去掉最外层括号的子表达式，并将结果重新加上括号
        sub_res.append("(" + dfs(part[0][1:-1]) + ")")
    else:
        # 否则递归处理每个子表达式
        for p in part:
            sub_res.append(dfs(p))

    # 排序所有子表达式，按照自定义的 compare 函数
    # 比较规则是，如果 a + b < b + a，则 a 应该排在 b 的前面
    return ''.join(sorted(sub_res, key=cmp_to_key(compare)))

# 调用 dfs 函数，计算并输出字典序最大的括号表达式
print(dfs(s))

cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 自定义比较器函数，比较两个字符串拼接后的字典序
bool compare(const string& a, const string& b) {
    return a + b < b + a;
}

// 深度优先搜索函数，递归处理括号表达式
string dfs(string s) {
    if (s.empty()) return "";
    
    vector<string> part;
    string now;
    int cnt = 0;
    
    // 分割括号表达式，按完整的括号对划分
    for (char c : s) {
        if (c == '(') cnt++;
        else cnt--;
        now += c;
        if (cnt == 0) { // 找到一个完整的括号对
            part.push_back(now);
            now.clear();
        }
    }

    vector<string> subRes;
    
    if (part.size() == 1) {
        // 如果只有一个完整的括号对，递归处理去掉最外层括号后的子表达式
        subRes.push_back("(" + dfs(part[0].substr(1, part[0].size() - 2)) + ")");
    } else {
        // 递归处理多个括号对
        for (string p : part) {
            subRes.push_back(dfs(p));
        }
    }

    // 排序子表达式，使得字典序最大
    sort(subRes.begin(), subRes.end(), compare);

    // 返回拼接后的结果
    string result;
    for (const string& str : subRes) {
        result += str;
    }
    return result;
}

int main() {
    string s;
    cin >> s; // 输入括号字符串
    cout << dfs(s) << endl; // 输出处理后的结果
    return 0;
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。