Check if one string can be converted to other using given operation | Function that prints whether is it possible to make a equal to T by performing given operations ; Base case , if we put the last character at front of A ; Base case , if we put the last character at back of A ; Condition if current sequence is matchable ; Condition for front move to ( i - 1 ) th character ; Condition for back move to ( i - 1 ) th character ; Condition if it is possible to make A equal to T ; Print final answer ; Driver Code
def twoStringsEquality ( s , t ) : NEW_LINE INDENT n = len ( s ) NEW_LINE dp = [ [ 0 for i in range ( n + 1 ) ] for i in range ( n ) ] NEW_LINE if ( s [ n - 1 ] == t [ 0 ] ) : NEW_LINE INDENT dp [ n - 1 ] [ 1 ] = 1 NEW_LINE DEDENT if ( s [ n - 1 ] == t [ n - 1 ] ) : NEW_LINE INDENT dp [ n - 1 ] [ 0 ] = 1 NEW_LINE DEDENT for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT for j in range ( n - i + 1 ) : NEW_LINE INDENT if ( dp [ i ] [ j ] ) : NEW_LINE INDENT if ( s [ i - 1 ] == t [ j ] ) : NEW_LINE INDENT dp [ i - 1 ] [ j + 1 ] = 1 NEW_LINE DEDENT if ( s [ i - 1 ] == t [ i + j - 1 ] ) : NEW_LINE INDENT dp [ i - 1 ] [ j ] = 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT ans = False NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT if ( dp [ 0 ] [ i ] == 1 ) : NEW_LINE INDENT ans = True NEW_LINE break NEW_LINE DEDENT DEDENT if ( ans == True ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S = " abab " NEW_LINE T = " baab " NEW_LINE twoStringsEquality ( S , T ) NEW_LINE DEDENT