1.如果s和t的头和尾不相等,因为头和尾少一个邻居,必然没法变,故输出-1
2.因为保证s[0]和s.back()与t相同,所以从1到s.size()-1遍历,
若s[i]和t[i] 不相等,有两种情况:
1.s[i]与其左右邻居不相等并且左右邻居和t的对应位置相等,则可以变s[i]。
(ps:s[i]改变后必定和左右邻居相等,那么左右邻居如果和t对应的位置不相等,则一定不能再改变了
2.如果不满足1的情况,即s[i]和左右邻居不相等,或者s[i]的左右邻居和t对应的位置不相等,那么
s和t便不相同,输出-1
只需要遍历一遍字符串,时间复杂度O(n)
上代码:
#include<iostream>
using namespace std;
const int N = 1000010;
int n;
int main()
{
cin >> n;
while(n --)
{
string t,s;
cin >> t >> s;
int ans = 0;
if(s[0] != t[0] || s.back() != t.back()) //开头和结尾不同,则一定不同
{
cout << "-1" << endl;
continue;
}
for(int i=1;i<s.size()-1;i++)
{
if(s[i] != t[i])
{
if(s[i-1] == t[i-1] && s[i+1] == t[i+1] && s[i] != s[i-1] && s[i] != s[i+1]) //保证邻居相同并且邻居和t对应的位置相同
ans ++;
else
{
ans = -1;
break;
}
}
}
cout << ans <<endl;
}
return 0;
}
为什么不用写是s[i]=t[i]