# Using Dynamic Programming to reduce time complexity

### 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.

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']))

• Could you elaborate on how exactly you get 3 for your example input? I don't really get what that "minimal space" means. Also, is this a programming challenge? If so, could you provide a link to it? If not, could you add more context, where does this problem come from? – Georgy Aug 29 '19 at 12:20
• The problem is from here. youtu.be/tOD6g7rF7NA – Santosh Prasad Aug 29 '19 at 18:29
• Please edit your question so that the title describes the purpose of the code, rather than its mechanism. We really need to understand the motivational context to give good reviews. Thanks! – Toby Speight Nov 1 '19 at 13:29

''' 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']))