Printing Shortest Common Supersequence | A dynamic programming based Java program print shortest supersequence of two strings ; returns shortest supersequence of X and Y ; dp [ i ] [ j ] contains length of shortest supersequence for X [ 0. . i - 1 ] and Y [ 0. . j - 1 ] ; Fill table in bottom up manner ; Below steps follow recurrence relation ; string to store the shortest supersequence ; Start from the bottom right corner and one by one push characters in output string ; If current character in X and Y are same , then current character is part of shortest supersequence ; Put current character in result ; reduce values of i , j and index ; If current character in X and Y are different ; Put current character of Y in result ; reduce values of j and index ; Put current character of X in result ; reduce values of i and index ; If Y reaches its end , put remaining characters of X in the result string ; If X reaches its end , put remaining characters of Y in the result string ; reverse the string and return it ; Swap values of left and right ; Driver code
class GFG { static String printShortestSuperSeq ( String X , String Y ) { int m = X . length ( ) ; int n = Y . length ( ) ; int dp [ ] [ ] = new int [ m + 1 ] [ n + 1 ] ; for ( int i = 0 ; i <= m ; i ++ ) { for ( int j = 0 ; j <= n ; j ++ ) { if ( i == 0 ) { dp [ i ] [ j ] = j ; } else if ( j == 0 ) { dp [ i ] [ j ] = i ; } else if ( X . charAt ( i - 1 ) == Y . charAt ( j - 1 ) ) { dp [ i ] [ j ] = 1 + dp [ i - 1 ] [ j - 1 ] ; } else { dp [ i ] [ j ] = 1 + Math . min ( dp [ i - 1 ] [ j ] , dp [ i ] [ j - 1 ] ) ; } } } String str = " " ; int i = m , j = n ; while ( i > 0 && j > 0 ) { if ( X . charAt ( i - 1 ) == Y . charAt ( j - 1 ) ) { str += ( X . charAt ( i - 1 ) ) ; i -- ; j -- ; } else if ( dp [ i - 1 ] [ j ] > dp [ i ] [ j - 1 ] ) { str += ( Y . charAt ( j - 1 ) ) ; j -- ; } else { str += ( X . charAt ( i - 1 ) ) ; i -- ; } } while ( i > 0 ) { str += ( X . charAt ( i - 1 ) ) ; i -- ; } while ( j > 0 ) { str += ( Y . charAt ( j - 1 ) ) ; j -- ; } str = reverse ( str ) ; return str ; } static String reverse ( String input ) { char [ ] temparray = input . toCharArray ( ) ; int left , right = 0 ; right = temparray . length - 1 ; for ( left = 0 ; left < right ; left ++ , right -- ) { char temp = temparray [ left ] ; temparray [ left ] = temparray [ right ] ; temparray [ right ] = temp ; } return String . valueOf ( temparray ) ; } public static void main ( String [ ] args ) { String X = " AGGTAB " ; String Y = " GXTXAYB " ; System . out . println ( printShortestSuperSeq ( X , Y ) ) ; } }