LeetCode 761. Special Binary String题目解析-wowAC

Description

Special binary strings are binary strings with the following two properties:

  • The number of 0's is equal to the number of 1's.

  • Every prefix of the binary string has at least as many 1's as 0's.

  • Given a special string S, a move consists of choosing two consecutive, non-empty, special substrings of S, and swapping them. (Two strings are consecutive if the last character of the first string is exactly one index before the first character of the second string.)

    At the end of any number of moves, what is the lexicographically largest resulting string possible?

    Example 1:

    Input: S = "11011000"
    Output: "11100100"
    Explanation:The strings "10" [occuring at S[1]] and "1100" [at S[3]] are swapped.
    This is the lexicographically largest string possible after some number of swaps.

    Note:

    1. S has length at most 50.

    2. S is guaranteed to be a special binary string as defined above.


题目复述

special binary string的定义如下:

  • 0的数量和1的数量相等

  • 串的任意前缀的1的数量大于等于0的数量

给定一个special string S,一个move操作定义如下,选择两个连续、非空的S串的子串,并且交换他们。(两个串是连续的当且仅当第一个串的最后一个字符后面是第二个串的第一个字符。)现在给定一个special string,经过任意步move操作之后,能得到的最大的串是什么?

题目解析

首先我们考虑解决此问题的简化版,给一些串的数组,现在需要将这些串拼成一个大串,每次只能交换相邻的串,求一个大串,此串的字典序最大。

例如S = ["abc", "def", "dee"],最后的结果为"defdeeabc"。

解决此问题需要将串从大到小排列并拼接即得到答案。比较的规则如下,例如a = "def", b =  "dee",我们将两个串拼接为ab和ba,因为ab(defdee) > ba(deedef),所以a > b,即结果串里面a的位置在b的前面会增大字典序。原因解释:因为每次可以比较相邻的串,因此我们可以通过三趟来找出最大,次大以及最小的串。是不是有点类似冒泡排序。

解决了上面的问题,考虑解决本问题,

  1. 对于S = “10 1100”来说,其由两个special string s1="10"和s2="1100"组成,为了让结果最大,只需要将他们排序组合即可。

  2. 对于S = “1 10 1100 0 1100”来说,其由两个special string s1="1 10 1100 0"和s2="1100"组成,其中s1还有其子special string,此时需要我们递归处理。

注意在提取special string的时候可以使用括号匹配的方法来进行。有没有发现对一个special string来说,将1看成‘(’,0看成')',此special string为一个合法的括号序列。

class Solution {
public:
    static bool cmp(const string& s1, const string &s2) { //比较两个串大小
        if(s1+s2 > s2+s1) return true;
        else return false;
    }
    string makeLargestSpecial(string S) {
        vector<string> sub_special;
        string res;
        
        int cnt = 0;
        int s = 0, e;
        for(e=0; e<S.size(); e++) {
            if(S[e] == '1') cnt++;
            else cnt--;
            if(cnt == 0) {
                sub_special.push_back("1"+makeLargestSpecial(S.substr(s+1, e-1-s))+"0"); //递归处理
                s = e+1;
            }
        }
        sort(sub_special.begin(), sub_special.end(), cmp); //排序
        for(int i=0; i<sub_special.size(); i++)
            res += sub_special[i];
        return res;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注