Check if given Strings can be made equal by inserting at most 1 String | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool areSimilar ( string S1 , string S2 ) { int N = S1 . size ( ) ; int M = S2 . size ( ) ; if ( N == M ) { if ( S1 == S2 ) return true ; return false ; } deque < string > X , Y ; S1 . push_back ( ' ▁ ' ) ; S2 . push_back ( ' ▁ ' ) ; string temp = " " ; for ( int i = 0 ; i < N + 1 ; i ++ ) { if ( S1 [ i ] == ' ▁ ' ) { X . push_back ( temp ) ; temp = " " ; } else { temp += S1 [ i ] ; } } for ( int i = 0 ; i < M + 1 ; i ++ ) { if ( S2 [ i ] == ' ▁ ' ) { Y . push_back ( temp ) ; temp = " " ; } else { temp += S2 [ i ] ; } } while ( X . size ( ) > 0 && Y . size ( ) > 0 && X . front ( ) == Y . front ( ) ) { X . pop_front ( ) ; Y . pop_front ( ) ; } while ( X . size ( ) > 0 && Y . size ( ) > 0 && X . back ( ) == Y . back ( ) ) { X . pop_back ( ) ; Y . pop_back ( ) ; } if ( X . size ( ) == 0 || Y . size ( ) == 0 ) return true ; return false ; } int main ( ) { string S1 = " Start ▁ practicing ▁ on ▁ GeeksforGeeks " ; string S2 = " Start ▁ GeeksforGeeks " ; if ( areSimilar ( S1 , S2 ) ) cout << " True " << endl ; else cout << " False " << endl ; return 0 ; }