Check if one string can be converted to other using given operation | C ++ implementation of above approach ; Function that prints whether is it possible to make a string 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 string A equal to string T ; Print final answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void twoStringsEquality ( string s , string t ) { int n = s . length ( ) ; vector < vector < int > > dp ( n , vector < int > ( n + 1 , 0 ) ) ; if ( s [ n - 1 ] == t [ 0 ] ) dp [ n - 1 ] [ 1 ] = 1 ; if ( s [ n - 1 ] == t [ n - 1 ] ) dp [ n - 1 ] [ 0 ] = 1 ; for ( int i = n - 1 ; i > 0 ; i -- ) { for ( int j = 0 ; j <= n - i ; j ++ ) { if ( dp [ i ] [ j ] ) { if ( s [ i - 1 ] == t [ j ] ) dp [ i - 1 ] [ j + 1 ] = 1 ; if ( s [ i - 1 ] == t [ i + j - 1 ] ) dp [ i - 1 ] [ j ] = 1 ; } } } bool ans = false ; for ( int i = 0 ; i <= n ; i ++ ) { if ( dp [ 0 ] [ i ] == 1 ) { ans = true ; break ; } } if ( ans == true ) cout << " Yes " << " STRNEWLINE " ; else cout << " No " << " STRNEWLINE " ; } int main ( ) { string S = " abab " ; string T = " baab " ; twoStringsEquality ( S , T ) ; return 0 ; }