3
\$\begingroup\$

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']))
\$\endgroup\$
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – Georgy Aug 29 at 12:20
  • \$\begingroup\$ The problem is from here. youtu.be/tOD6g7rF7NA \$\endgroup\$ – Santosh Prasad Aug 29 at 18:29
  • 1
    \$\begingroup\$ 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! \$\endgroup\$ – Toby Speight Nov 1 at 13:29
0
\$\begingroup\$

''' 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']))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.