Using Dynamic Programming to reduce time complexity

Question

Input

A long string of numbers, A list of numbers in string

Output

Minimum space needed in long string to match maximum numbers from list

Example

• minSpaces('3141592653589793238462643383279',['314','49','15926535897','14','9323','8462643383279','4','793'])
• will return 3

I am using below code to solve it, but I am not able to figure out how can I use DP for more efficient time complexity.

Thanks for your help.

dpArr = {} #empty list for DP

def findMinSpaces(k, piStr, favNumArr):
    curr = ''
    ans = 0
    N = len(piStr)
    if( k == N):
        return 0
    for i in range(k, N):
        print(curr)
        curr += piStr[i]
        if(curr in favNumArr and i != N-1):
            if(curr not in dpArr):
                ans += 1 + findMinSpaces(i+1, piStr, favNumArr)
                dpArr[curr] = ans
            else:
                print("from dpArr")
                return dpArr[curr]    
    print(dpArr)
    return ans            


def minSpaces(piStr, favNumArr):
    return findMinSpaces(0, piStr, favNumArr)
print(minSpaces('3141592653589793238462643383279',['314','49','15926535897','14','9323','8462643383279','4','793']))

Answer 1

''' The Problem can be thought as string pattern matching, Where output will be minimum no of spaces in bigger string(piStr) to match maximum no of strings from list of smaller strings(favNumArr). To solve this, we take one var "ans" to store no spaces and one variable "curr" to store the current pattern. Now we iterate through the piStr and whenever we encounter(ith pos) that curr pattern is in favNumArr, we use recursion and call findMinSpaces for i+1 and increment ans with 1. There is no need to use DP if we return from the loop with first occurrence of match and hence the loop will not run after it return value of recursion call. The last return statement is to counter when i == N-1 when we reach the end of piStr. The time complexity for this solution is O(n) Any suggestion for further enhancement or if breaks any edge case is open.'''

def findMinSpaces(k, piStr, favNumArr):
    curr = ''
    ans = 0
    N = len(piStr)
    if( k == N):
        return 0
    for i in range(k, N):
        print(curr)
        curr += piStr[i]
        if(curr in favNumArr and i != N-1):
            ans += 1 + findMinSpaces(i+1, piStr, favNumArr)
            return ans
    return ans            

def minSpaces(piStr, favNumArr):
    return findMinSpaces(0, piStr, favNumArr)

print(minSpaces('',['3149v','40x9','15926535c897','1c4','932c3','84626c43383279','4c793']))