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']))
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? \$\endgroup\$ – Georgy Aug 29 '19 at 12:20