Shortest Uncommon Subsequence | A dynamic programming based C ++ program to find shortest uncommon subsequence . ; Returns length of shortest common subsequence ; declaring 2D array of m + 1 rows and n + 1 columns dynamically ; T string is empty ; S string is empty ; char not present in T ; Driver program to test the above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  1005 NEW_LINE int shortestSeq ( char * S , char * T ) { int m = strlen ( S ) , n = strlen ( T ) ; int dp [ m + 1 ] [ n + 1 ] ; for ( int i = 0 ; i <= m ; i ++ ) dp [ i ] [ 0 ] = 1 ; for ( int i = 0 ; i <= n ; i ++ ) dp [ 0 ] [ i ] = MAX ; for ( int i = 1 ; i <= m ; i ++ ) { for ( int j = 1 ; j <= n ; j ++ ) { char ch = S [ i - 1 ] ; int k ; for ( k = j - 1 ; k >= 0 ; k -- ) if ( T [ k ] == ch ) break ; if ( k == -1 ) dp [ i ] [ j ] = 1 ; else dp [ i ] [ j ] = min ( dp [ i - 1 ] [ j ] , dp [ i - 1 ] [ k ] + 1 ) ; } } int ans = dp [ m ] [ n ] ; if ( ans >= MAX ) ans = -1 ; return ans ; } int main ( ) { char S [ ] = " babab " ; char T [ ] = " babba " ; int m = strlen ( S ) , n = strlen ( T ) ; cout << " Length ▁ of ▁ shortest ▁ subsequence ▁ is ▁ : ▁ " << shortestSeq ( S , T ) << endl ; }