Check if given Strings can be made equal by inserting at most 1 String | Python3 program for the above approach ; Function to check whether two sentences can be made equal by inserting at most one sentence in one of them ; Size of sentence S1 ; Size of sentence S2 ; Check if S1 and S2 are of equal sizes ; If both sentences are the same , return True ; Otherwise , return false ; Declare 2 deques X and Y ; Insert ' ▁ ' at the end of both sentences so that the last word can be identified ; Traverse the sentence S1 ; Push temp in deque when a space comes in sentence i . e a word has been formed ; temp stores words of the sentence ; Traverse the sentence S1 ; Push temp in deque when a space comes in sentence i . e a word has been formed ; temp stores words of the sentence ; Check for prefixes of both sentences ; Pop the prefix from both deques till they are equal ; Check for suffixes of both sentences ; Pop the suffix from both deques till they are equal ; If any of the deques is empty return True ; If both the deques are not empty return false ; Driver code ; Input ; Function call
from collections import deque NEW_LINE def areSimilar ( S1 , S2 ) : NEW_LINE INDENT S1 = [ i for i in S1 ] NEW_LINE S2 = [ i for i in S2 ] NEW_LINE N = len ( S1 ) NEW_LINE M = len ( S2 ) NEW_LINE if ( N == M ) : NEW_LINE INDENT if ( S1 == S2 ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT X , Y = deque ( ) , deque ( ) NEW_LINE S1 . append ( ' ▁ ' ) NEW_LINE S2 . append ( ' ▁ ' ) NEW_LINE temp = " " NEW_LINE for i in range ( N + 1 ) : NEW_LINE INDENT if ( S1 [ i ] == ' ▁ ' ) : NEW_LINE INDENT X . append ( temp ) NEW_LINE temp = " " NEW_LINE DEDENT else : NEW_LINE INDENT temp += S1 [ i ] NEW_LINE DEDENT DEDENT for i in range ( M + 1 ) : NEW_LINE INDENT if ( S2 [ i ] == ' ▁ ' ) : NEW_LINE INDENT Y . append ( temp ) NEW_LINE temp = " " NEW_LINE DEDENT else : NEW_LINE INDENT temp += S2 [ i ] NEW_LINE DEDENT DEDENT while ( len ( X ) > 0 and len ( Y ) > 0 and X [ 0 ] == Y [ 0 ] ) : NEW_LINE INDENT X . popleft ( ) NEW_LINE Y . popleft ( ) NEW_LINE DEDENT while ( len ( X ) > 0 and len ( Y ) > 0 and X [ - 1 ] == Y [ - 1 ] ) : NEW_LINE INDENT X . pop ( ) NEW_LINE Y . pop ( ) NEW_LINE DEDENT if ( len ( X ) == 0 or len ( Y ) == 0 ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S1 = " Start ▁ practicing ▁ on ▁ GeeksforGeeks " NEW_LINE S2 = " Start ▁ GeeksforGeeks " NEW_LINE if ( areSimilar ( S1 , S2 ) ) : NEW_LINE INDENT print ( " True " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " False " ) NEW_LINE DEDENT DEDENT