2 条题解
-
2
题意
给你两串由 '0' 和 '1' 构成的字符串 a 和 b,你可以对 a 串进行操作,在一次操作之中,你可以选择 01 串前缀中01数量相等的前缀,使其字母颠倒(0 变成 1 , 1 变成 0)。
现在你可以进行任意次操作,问你能否让 a和 b 两个字符串相等。
思路
因为可以进行任意次操作,所以只要选择的前缀01数量相同无论如何都可以转回来,所以重点就在01的数量是否相同。
所以可以在从前都后进行遍历的时候计算前缀中01的数量,当遍历时遇到:
(1)a[i]==b[i]&&a[i+1]!=b[i+1] (2)a[i]!=b[i]&&a[i+1]==b[i+1]
上述两种情况就代表此时字符串 1~i 的前缀必须要进行一次翻转,则此时判断 a 串 1~i 的前缀中01个数是否相同,若不相同则代表不能翻转,则中止遍历,输出 NO,若相同就代表此时可以翻转,继续向后遍历,直到遍历结束输出 YES 或在遇到上述输出 NO 的条件的情况下中止遍历输出 NO。
信息
- ID
- 1026
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 85
- 已通过
- 11
- 上传者