Count of non | Python 3 program for the above approach ; Define the dp table globally ; Recursive function to calculate total number of valid non - decreasing strings ; If already calculated state ; Base Case ; Stores the total count of strings formed ; Fill the value in dp matrix ; Function to find the total number of non - decreasing string formed by replacing the '? ; Initialize all value of dp table with - 1 ; Left and Right limits ; Iterate through all the characters of the string S ; Change R to the current character ; Call the recursive function ; Change L to R and R to 9 ; Reinitialize the length of ? to 0 ; Increment the length of the segment ; Update the ans ; Return the total count ; Driver Code
MAXN = 100005 NEW_LINE dp = [ [ - 1 for x in range ( 10 ) ] for y in range ( MAXN ) ] NEW_LINE def solve ( len , gap ) : NEW_LINE INDENT if ( dp [ len ] [ gap ] != - 1 ) : NEW_LINE INDENT return dp [ len ] [ gap ] NEW_LINE DEDENT if ( len == 0 or gap == 0 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( gap < 0 ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT ans = 0 NEW_LINE for i in range ( gap + 1 ) : NEW_LINE INDENT ans += solve ( len - 1 , gap - i ) NEW_LINE DEDENT dp [ len ] [ gap ] = ans NEW_LINE return dp [ len ] [ gap ] NEW_LINE DEDENT ' NEW_LINE def countValidStrings ( S ) : NEW_LINE INDENT global dp NEW_LINE N = len ( S ) NEW_LINE L , R = 1 , 9 NEW_LINE cnt = 0 NEW_LINE ans = 1 NEW_LINE for i in range ( N ) : NEW_LINE INDENT if ( S [ i ] != ' ? ' ) : NEW_LINE INDENT R = ord ( S [ i ] ) - ord ( '0' ) NEW_LINE ans *= solve ( cnt , R - L ) NEW_LINE L = R NEW_LINE R = 9 NEW_LINE cnt = 0 NEW_LINE DEDENT else : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT DEDENT ans *= solve ( cnt , R - L ) NEW_LINE return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT S = "1 ? ? ?2" NEW_LINE print ( countValidStrings ( S ) ) NEW_LINE DEDENT