思路如下(正难硬做):
- 找到第一个字符串所有可以互相交换的集合,记录每个集合的左边界,右边界,0的数量,1的数量。第二个字符串同理。
- 第一次对比两个字符串,若同一位置二字符串出现同样的且都不在任意一集合的字符,直接
ans++;;
- 若同一位置有一字符串出现不能交换的字符,而另一字符串该位置在一集合内,则看这个集合还有没有该字符,有则
ans++,该集合此字符数量--;无则该集合另一种类字符数量--;
- 若同一位置二字符串字符均在集合内,标记;
- 第二次对比两个字符串,发现有标记的地方检查该处对应的二集合是否都还剩有0或都还剩有1,有则
ans++;二集合对应的字符数量均--;
- 输出ans。
我简直难以评价我的做法,花了2.5h,写了5.0kb的狮山,但是大小样例都过了,因此求问正确性或hack。