思路

水题没必要写得像楼上那么复杂吧…… 从左到右出现和目标状态不同的字符和下一个字符改变, 这个操作的次数就是答案了,递推复杂度O(n)

代码

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;

string str1,str2;
int A[N],B[N],n,ans=0; 

signed main(){
//	ios::sync_with_stdio(0);//	cin.tie(0);cout.tie(0);
//  freopen("in.cpp","r",stdin);freopen("out.cpp","w",stout);
	cin>>str1>>str2;
	n=str1.length();
	for(int i=0;i<n;i++){
		if(str1[i]=='*') A[i]=0;
		else A[i]=1;
	}
	for(int i=0;i<n;i++){
		if(str2[i]=='*') B[i]=0;
		else B[i]=1;
	}
	for(int i=0;i<n-1;i++){
		if(A[i]!=B[i]){
			ans++;
			A[i]^=1;
			A[i+1]^=1;
		}
	}
	cout<<ans<<"\n";
	return 0;
}