leetcode：761. 特殊的二进制序列【递归 + 转换有效括号】

分析

每次只能操作一个有效的括号串
我们通过cur来记录什么时候是一个最短的有效串，用last记录起点
显然有效串的一头一尾我们不可能动，能动的只有中间的地方，让他们内部串再次组合变得最大（递归）
最后把最外层的所有有效串按字典序倒序排即可

ac code

class Solution:
    def makeLargestSpecial(self, s: str) -> str:
        cur, last = 0, 0
        ret = []
        for i, c in enumerate(s):
            cur += (1 if c == '1' else -1)
            # 一个有效串
            if cur == 0:
                # 内部串再次排序
                # 一头一尾不动
                ret.append('1' + self.makeLargestSpecial(s[last + 1: i]) + '0')
                last = i + 1
        
        return ''.join(sorted(ret, reverse = True))

总结

递归求解