Count the number of ways to construct the target string | Java Program to Count the number of ways to construct the target String ; base case ; If current subproblem has been solved , use the value ; search through all the indiced at which the current character occurs . For each index greater than prev , take the index and move to the next position , and add to the answer . ; Store and return the solution for this subproblem ; preprocess the Strings by storing for each character of every String , the index of their occurrence we will use a common list for all because of only the index matter in the String from which the character was picked ; we are storing j + 1 because the initial picked index in the recursive step will ne 0. This is just for ease of implementation ; initialise dp table . - 1 represents that the subproblem hasn 't been solved ; Driver Code
import java . util . * ; class GFG { static int mod = 1000000007 ; static int [ ] [ ] dp = new int [ 1000 ] [ 1000 ] ; static int calculate ( int pos , int prev , String s , Vector < Integer > index ) { if ( pos == s . length ( ) ) return 1 ; if ( dp [ pos ] [ prev ] != - 1 ) return dp [ pos ] [ prev ] ; int answer = 0 ; for ( int i = 0 ; i < index . size ( ) ; i ++ ) { if ( index . get ( i ) . compareTo ( prev ) >= 0 ) { answer = ( answer % mod + calculate ( pos + 1 , index . get ( i ) , s , index ) % mod ) % mod ; } } return dp [ pos ] [ prev ] = answer ; } static int countWays ( Vector < String > a , String s ) { int n = a . size ( ) ; Vector < Integer > [ ] index = new Vector [ 26 ] ; for ( int i = 0 ; i < 26 ; i ++ ) index [ i ] = new Vector < Integer > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < a . get ( i ) . length ( ) ; j ++ ) { index [ a . get ( i ) . charAt ( j ) - ' a ' ] . add ( j + 1 ) ; } } for ( int i = 0 ; i < 1000 ; i ++ ) { for ( int j = 0 ; j < 1000 ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } return calculate ( 0 , 0 , s , index [ 0 ] ) ; } public static void main ( String [ ] args ) { Vector < String > A = new Vector < String > ( ) ; A . add ( " adc " ) ; A . add ( " aec " ) ; A . add ( " erg " ) ; String S = " ac " ; System . out . print ( countWays ( A , S ) ) ; } }