text: Count the number of ways to construct the target string | C # 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
code: using System ; using System . Collections . Generic ; class GFG { static int mod = 1000000007 ; static int [ , ] dp = new int [ 1000 , 1000 ] ; static int calculate ( int pos , int prev , String s , List < int > 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 . Count ; i ++ ) { if ( index [ i ] . CompareTo ( prev ) >= 0 ) { answer = ( answer % mod + calculate ( pos + 1 , index [ i ] , s , index ) % mod ) % mod ; } } return dp [ pos , prev ] = answer ; } static int countWays ( List < String > a , String s ) { int n = a . Count ; List < int > [ ] index = new List < int > [ 26 ] ; for ( int i = 0 ; i < 26 ; i ++ ) index [ i ] = new List < int > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < a [ i ] . Length ; j ++ ) { index [ a [ i ] [ 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 ) { List < String > A = new List < String > ( ) ; A . Add ( " adc " ) ; A . Add ( " aec " ) ; A . Add ( " erg " ) ; String S = " ac " ; Console . Write ( countWays ( A , S ) ) ; } }