Check if it is possible to transform one string to another | function to check if a string can be converted to another string by performing following operations ; calculates length ; mark 1 st position as true ; traverse for all DPi , j ; if possible for to convert i characters of s1 to j characters of s2 ; if upper_case ( s1 [ i ] ) == s2 [ j ] is same ; if not upper then deletion is possible ; driver code
def check ( s1 , s2 ) : NEW_LINE INDENT n = len ( s1 ) NEW_LINE m = len ( s2 ) NEW_LINE dp = ( [ [ False for i in range ( m + 1 ) ] for i in range ( n + 1 ) ] ) NEW_LINE dp [ 0 ] [ 0 ] = True NEW_LINE for i in range ( len ( s1 ) ) : NEW_LINE INDENT for j in range ( len ( s2 ) + 1 ) : NEW_LINE INDENT if ( dp [ i ] [ j ] ) : NEW_LINE INDENT if ( ( j < len ( s2 ) and ( s1 [ i ] . upper ( ) == s2 [ j ] ) ) ) : NEW_LINE INDENT dp [ i + 1 ] [ j + 1 ] = True NEW_LINE DEDENT if ( s1 [ i ] . isupper ( ) == False ) : NEW_LINE INDENT dp [ i + 1 ] [ j ] = True NEW_LINE DEDENT DEDENT DEDENT DEDENT return ( dp [ n ] [ m ] ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT s1 = " daBcd " NEW_LINE s2 = " ABC " NEW_LINE if ( check ( s1 , s2 ) ) : NEW_LINE INDENT print ( " YES " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " NO " ) NEW_LINE DEDENT DEDENT