Check if given string can be formed by two other strings or their permutations | Python 3 implementation of the approach ; Function to sort the given string using counting sort ; Array to store the count of each character ; Insert characters in the string in increasing order ; Function that returns true if str can be generated from any permutation of the two strings selected from the given vector ; Sort the given string ; Select two strings at a time from given vector ; Get the concatenated string ; Sort the resultant string ; If the resultant string is equal to the given string str ; No valid pair found ; Driver code
MAX = 26 NEW_LINE def countingsort ( s ) : NEW_LINE INDENT count = [ 0 for i in range ( MAX ) ] NEW_LINE for i in range ( len ( s ) ) : NEW_LINE INDENT count [ ord ( s [ i ] ) - ord ( ' a ' ) ] += 1 NEW_LINE DEDENT index = 0 NEW_LINE for i in range ( MAX ) : NEW_LINE INDENT j = 0 NEW_LINE while ( j < count [ i ] ) : NEW_LINE INDENT s = s . replace ( s [ index ] , chr ( 97 + i ) ) NEW_LINE index += 1 NEW_LINE j += 1 NEW_LINE DEDENT DEDENT DEDENT def isPossible ( v , str1 ) : NEW_LINE INDENT countingsort ( str1 ) ; NEW_LINE for i in range ( len ( v ) - 1 ) : NEW_LINE INDENT for j in range ( i + 1 , len ( v ) , 1 ) : NEW_LINE INDENT temp = v [ i ] + v [ j ] NEW_LINE countingsort ( temp ) NEW_LINE if ( temp == str1 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT DEDENT return True NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT str1 = " amazon " NEW_LINE v = [ " fds " , " oxq " , " zoa " , " epw " , " amn " ] NEW_LINE if ( isPossible ( v , str1 ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT