链接：https://leetcode.cn/problems/special-binary-string/solution/di-gui-by-xun-ge-v-hk6l/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

解题思路
对于本题，需要对10这种特殊二进制序列按字典序排序，我们可以将1,0进行简单类比一下

• 将 1 当成（
• 将 0 当成 ）

其实题目就相当于是括号匹配了，题意 -> 需要我们对已经左右匹配好的括号字符串，进行排序，每次排序选择的最小单位为一对有效括号，比尽可能多的将（ 排在前面

比如：11011000 -> ( () (()) ) 对于整体而言是一个有效括号序列，然后以一对有效括号为最小单位对其排序

具体实现看代码，注释超级详细

代码

static inline int cmp(const void* pa, const void* pb) {//比较返回字典序大的字符串
    return strcmp(*(char **)pb, *(char **)pa);
}
//递归实现字符串的分治，就是分割符号要求的子串
char *helper(char *s, int start, int end) {
    int len = end - start + 1;
    // if(len == 0)//可以包含在下面情况
    // {
    //     return "";
    // }
    if(len <= 2)//len<=2,为最简符合要求子串，为1,0或者空，也是递归出口
    {
        char * ans = malloc(sizeof(char) * (len+1));
        strncpy(ans, s+start, len);
        ans[len] = '\0';
        return ans;
    }
    char ** res = malloc(sizeof(char *) * len);
    int resSize = 0;
    int conut = 0;
    int left = start;
    while(start <= end)//遍历字符串，寻找符合要求子串
    {
        if(s[start] == '1')
        {
            conut++;
        }
        else
        {
            conut--;
            if(conut == 0)//符合要求子串
            {
                res[resSize] = malloc(sizeof(char) * (start - left + 3));//申请空间保存子串
                char * r = helper(s, left+1, start-1);//递归寻找最简子串
                sprintf(res[resSize], "%s%s%s", "1", r, "0");//合并子串
                resSize++;
                left = start+1;
            }
        }
        start++;
    }
    int p = 0;
    qsort(res, resSize, sizeof(char *), cmp);//按字典序降序
    char * a = malloc(sizeof(char) * (len+1));
    for(int i = 0; i < resSize; i++)//保存子串位置
    {
        p += sprintf(a+p, "%s", res[i]);
        free(res[i]);
    }
    return a;//返回最佳子串
}

char * makeLargestSpecial(char * s) {
    int len = strlen(s);
    return helper(s, 0, len - 1);
}

作者：xun-ge-v
链接：https://leetcode.cn/problems/special-binary-string/solution/di-gui-by-xun-ge-v-hk6l/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。