Problem: leetcode 困难题 761. Special Binary String 特殊的二进制序列

解题过程

这题目的描述有问题，下面注释掉的就是递归做的，这是我的理解：第一次交换以后的字符串接着做第二次交换，接着做第三次交换，每次递归的输入长度都是最开始输入的s.size()，而不是分片以后的长度，然后拿到最大的字符串

看了官方题解，感觉和题目的描述不太相同，官方题解使用了分片，也就是找到这个字符串所有的分片然后重排合并，并不是交换一次以后继续递归

Code

class Solution {
public:
    string makeLargestSpecial(string s) {
        if(s.size() <= 2) return s;
        int cnt = 0, left = 0;
        vector<string> subs;
        for(int i = 0; i < s.size(); i++) {
            if(s[i]=='1') cnt++;
            else {
                cnt--;
                if(cnt==0) {
                    subs.push_back("1" + makeLargestSpecial(s.substr(left + 1, i - left - 1)) + "0");
                    left = i + 1;
                }
            }
        }
        sort(subs.begin(), subs.end(), greater<string>());
        string tmp;
        for(int i = 0; i < subs.size(); i++) {
            tmp += subs[i];
        }
        return tmp;
    }
};

/*
class Solution {
public:
    string ret;
    bool check(string tg) {
        int a = 0, z = 0;
        for(char& c : tg) {
            if(c=='1') a++;
            else z++;
            if(a < z) return false;
        }
        return true;
    }
    unordered_set<string> te;
    string makeLargestSpecial(string s) {
        for(int w = 0; w < s.size(); w++) {
            while(w < s.size() && s[w]=='0') w++;
            if(w>= s.size()) continue;
            int a = 0, z = 0;
            string s1, s2, t1, t2;
            for(int i = w; i < s.size(); i++) {
                if(s[i]=='1') a++;
                else z++;
                if(a == z) {
                    int aa = 0, zz = 0, ww = i + 1;
                    while(ww < s.size() && s[ww]=='0') ww++;
                    if(ww < s.size()) {
                        for(int j = ww; j < s.size(); j++) {
                            if(s[j]=='1') aa++;
                            else zz++;
                            if(aa == zz) {
                                t1 = s1 = s.substr(w, i - w + 1);
                                t2 = s2 = s.substr(ww, j - ww + 1);
                                if(s1.size()!=0 && s2.size()!=0 && s1!=s2 && check(t1) && check(t2)) {
                                    string prefix, tail, mid, now, rec;
                                    prefix = s.substr(0, w);
                                    if(j+1 < s.size()) tail = s.substr(j+1);
                                    if(i+1 < ww) mid = s.substr(i+1, ww - i - 1);
                                    if(s1.size() < s2.size()) {
                                        s1 += string(s2.size()-s1.size(), '0');
                                    } else {
                                        s2 += string(s1.size() - s2.size(), '0');
                                    }
                                    if(s1 < s2) {
                                        now = prefix + t2 + mid + t1 + tail;
                                        if(check(now)) {
                                            ret = max(ret, now);
                                            // if(now > s) {
                                                if(te.find(ret)== te.end()) {
                                                    te.insert(ret);
                                                    rec = makeLargestSpecial(ret);
                                                    ret = max(ret, rec);
                                                }
                                            // }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        return ret.size()==0? s:ret;
    }
};
*/