Shortest possible combination of two strings | Java program to print supersequence of two strings ; Prints super sequence of a [ 0. . m - 1 ] and b [ 0. . n - 1 ] ; Fill table in bottom up manner ; Below steps follow above recurrence ; Create a string of size index + 1 to store the result ; Start from the right - most - bottom - most corner and one by one store characters in res [ ] ; If current character in a [ ] and b are same , then current character is part of LCS ; Put current character in result ; reduce values of i , j and indexs ; If not same , then find the larger of two and go in the direction of larger value ; Copy remaining characters of string ' a ' ; Copy remaining characters of string ' b ' ; Print the result ; Driver program to test above function
public class GFG_1 { String a , b ; static void printSuperSeq ( String a , String b ) { int m = a . length ( ) , n = b . 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 ( a . charAt ( i - 1 ) == b . 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 res = " " ; int i = m , j = n ; while ( i > 0 && j > 0 ) { if ( a . charAt ( i - 1 ) == b . charAt ( j - 1 ) ) { res = a . charAt ( i - 1 ) + res ; i -- ; j -- ; } else if ( dp [ i - 1 ] [ j ] < dp [ i ] [ j - 1 ] ) { res = a . charAt ( i - 1 ) + res ; i -- ; } else { res = b . charAt ( j - 1 ) + res ; j -- ; } } while ( i > 0 ) { res = a . charAt ( i - 1 ) + res ; i -- ; } while ( j > 0 ) { res = b . charAt ( j - 1 ) + res ; j -- ; } System . out . println ( res ) ; } public static void main ( String args [ ] ) { String a = " algorithm " ; String b = " rhythm " ; printSuperSeq ( a , b ) ; } }