### shakil_AUST's blog

By shakil_AUST, 8 years ago,

Can anyone please tell me the process how to solve this problem . Thanx in advance :)

• +11

 » 8 years ago, # |   +4 Solved the problem after seeing this post. lets take dp[flip_allowed][flipped][i][j][k]=minimum number of flip needed to match x[i....j] with Y[k ..... k+j-i], 'filp_allowed' and 'flipped' are boolean values that denotes whether we are allowed to flip the current segment X[i....j] and whether the portion x[i....j] is flipped respectively. now to match x[....] to y[...], we can either flip the entire segment x[....] , or we will at least leave one character from any end of x[i....j] if that matches Y[k ........ k+j-i]. So the state transitions will look like this if(flip_allowed) dp[filp_allowed][flipped][i][j][k] = 1 + dp[0][!flipped][i][j][k]; if(!flipped) { if(X[i]==Y[k]) dp[flip_allowed][flipped][i][j][k]=dp[1][0][i+1][j][k+1]; if(X[j]==Y[k+j-i]) dp[flop_allowed][flipped][i][j][k]=dp[1][0][i][j-1][k]; } else if(flipped) { if(X[j]==Y[k]) dp[flip_allowed][flipped][i][j][k]=dp[1][1][i][j-1][k+1]; if(X[i]==Y[k+j-i]) dp[flip_allowed][flipped][i][j][k]=dp[1][1][i+1][j][k]; } Hope that helps.
•  » » 8 years ago, # ^ |   0 shopnobaj_raju Thanx a lot vaiya :)