Count the number of ways to construct the target string | Python 3 Program to Count the number of ways to construct the target string ; base case ; If current subproblem has been solved , use the value ; current character ; 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 solve ; Driver Code
mod = 1000000007 NEW_LINE dp = [ [ - 1 for i in range ( 1000 ) ] for j in range ( 1000 ) ] ; NEW_LINE def calculate ( pos , prev , s , index ) : NEW_LINE INDENT if ( pos == len ( s ) ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( dp [ pos ] [ prev ] != - 1 ) : NEW_LINE INDENT return dp [ pos ] [ prev ] NEW_LINE DEDENT c = ord ( s [ pos ] ) - ord ( ' a ' ) ; NEW_LINE answer = 0 NEW_LINE for i in range ( len ( index ) ) : NEW_LINE INDENT if ( index [ i ] > prev ) : NEW_LINE INDENT answer = ( answer % mod + calculate ( pos + 1 , index [ i ] , s , index ) % mod ) % mod NEW_LINE DEDENT DEDENT dp [ pos ] [ prev ] = 4 NEW_LINE return dp [ pos ] [ prev ] NEW_LINE DEDENT def countWays ( a , s ) : NEW_LINE INDENT n = len ( a ) NEW_LINE index = [ [ ] for i in range ( 26 ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( len ( a [ i ] ) ) : NEW_LINE INDENT index [ ord ( a [ i ] [ j ] ) - ord ( ' a ' ) ] . append ( j + 1 ) ; NEW_LINE DEDENT DEDENT return calculate ( 0 , 0 , s , index [ 0 ] ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = [ ] NEW_LINE A . append ( " adc " ) NEW_LINE A . append ( " aec " ) NEW_LINE A . append ( " erg " ) NEW_LINE S = " ac " NEW_LINE print ( countWays ( A , S ) ) NEW_LINE DEDENT