lc761.SpecialBinaryString

https://leetcode.com/problems/special-binary-string/description/

符合两个规则的01字符串称为s串&＃xff1a;

1.   0和1的数量相同

2.  任意前缀0不能多于1

其实这样子限制的是一个合法嵌套括号。

然后&＃xff0c;要求的是&＃xff0c;相邻的子s串可以换位置&＃xff0c;让你输出字典序最大的交换结果。

发现规律&＃xff1a;

只要给定串是s串&＃xff0c;那么

任何1开始都能开启一段s串

s串的关系只有两种&＃xff0c;相邻和嵌套。

现在的问题是&＃xff0c;在做分析的时候&＃xff0c;一个从1开始的字串是选最长的还是最短&＃xff1f;

答案&＃xff1a;选最短&＃xff01;

选最短就保证了寻找所有可能&＃xff0c;而已若a是最短字串&＃xff0c;那么a必须以1开始以0结尾&＃xff0c;把这两段去除后里面要不就是空&＃xff0c;要不就是若干s串相邻。

对于这种嵌套&＃xff0c;递归的做可以。因为不相邻的不能交换&＃xff0c;那么就不用考虑outside的情况了。

有个小语法&＃xff0c;list的倒置是list[::-1]第三个参数是步长&＃xff0c;所以取-1正好。

code&＃xff1a;

class Solution:def makeLargestSpecial(self, S):count &＃61; i &＃61; 0res &＃61; []for j, v in enumerate(S):count &＃61; count &＃43; 1 if v &＃61;&＃61; &＃39;1&＃39; else count - 1if count &＃61;&＃61; 0:res.append(&＃39;1&＃39; &＃43; self.makeLargestSpecial(S[i &＃43; 1:j]) &＃43; &＃39;0&＃39;)i &＃61; j &＃43; 1return &＃39;&＃39;.join(sorted(res)[::-1])

View Code