Minimum amount of spaces inserted in a given string, such that it gets composed only of elements from a given list

Question

The Challenge

Given a big string and a list of smaller strings, find the minimum amount of spaces that must be inserted between characters of the string in such way that it becomes composed only of elements from the list of smaller strings. (and which are the respective elements used). [Python 3]

For instance, if you had as a string: 'foobarpy' and as a list: ['foo', 'bar', 'py', 'foob', 'arpy'], the optimal solution would be: foob arpy, requiring you to insert only a single space in the string.

Basically:

-The "big string" must be "transformed" into a combination of elements from the list, only by inserting spaces in between characters of it (with the least amount of spaces as possible)

-Elements can't be repeated

-Not all the elements must be used

# Sample input
big_string = '3141592653589793238462643383279'
small_strings = ['3', '314', '49', '9001', '15926535897', '14', '9323', '8462643383279', '4', '793', '3141592653589793238462643383278', '314159265358979','3238462643383279']

My Solution

As I see it, instead of trying to "slice" the given string, it's easier to try to combine the elements from the list and look for the match with the least elements. My full code: https://repl.it/@LucasWerner/String-Least-Spacing

1. Get rid of elements in the list that don't appear in the string.

# Required modules
import itertools
import numpy as np 

small_strings = [x for x in small_strings if x in big_string]

2. Combine elements in groups of sizes from 1 to the length of the list (just gathering to whole thing together) and check whether the combination has the same length as the given string... that would select fewer possibilites to further analyze. Store the possibilites as a list of tuples.

possibilites = list()
for k in range(1, len(small_strings)): #k is the size of the combination
  c = list(itertools.combinations(small_strings, k))
  combinations =  [x for x in c if sum(len(i) for i in x) == big_string_len]
  possibilites.extend(combinations)

3. Permutate the tuples inside the list to see if they match the big_string. If so, store the permutated tuple in a list of matches.

matches = list()
for tup in possibilites:
  p = list(itertools.permutations(tup))
  permutations = [x for x in p if ''.join(x) == big_string]
  matches.extend(permutations)

4. Bind the matches with their lengths in a dictionary

sizes = dict()
for tup in matches:
  sizes[tup] = len(tup)

5. Finding the optimal solution (minimal length and where it occurres)

min_key = min(sizes, key=sizes.get)
min_val = sizes[min_key]

6. Giving the optimal solution

print('Best solution is', ' '.join(min_key), 'with', min_val - 1, 'space(s)')

Which in this case would print:

Best solution is 314159265358979 3238462643383279 with 1 space(s)

It's my first month learning Python and I was really hoping to get some feedback and tips from far more experient programmers about what I could change/learn/improve in the code to make it better/more efficient.

Answer 1

Firstly, great job on creating a solution that works. That is often the first step in creating an optimal solution.

But as you may have noticed, making combinations and permutations based on the number of elements in small_strings will start to scale incredibly as you process longer and longer small_strings arrays.

Mathematically, your solution is concise and straight-forward-- kudos again to that. The approach I will suggest is based on Dynamic Programming and preprocessing. This is to speed up scenarios where you have a very large (>100) number of small_strings.

---

This approach will use the fact that we can solve the whole problem in the same manner of solving a subset of the problem. Specifically, if we can construct the big_string piece by piece, then we can simply add the result of the part we have constructed and add/recurse it on the rest of the string.

The first idea to consider is building a trie for the strings in small_strings. Also known as a prefix tree, a trie will help us figure out which strings we can use to 'construct' the big_string. I highly recommend understanding the concept of a trie for further insight into this problem.

Secondly, we want to implement a function that explores the problem space in a way that is efficient and breaks on paths that yield no results. This is typical of many DP (Dynamic Programming) problems and often looks like recursion in practice. Knowing when and how to implement this comes with practice. I also highly recommend practicing some classical DP problems if you want to become a skilled developer.

With those points in mind, here's a solution:

def buildTrie(words):
    trie = {}
    for word in words:
        current = trie
        for c in word:
            current = current.setdefault(c, {})
        current['isWord'] = word

    return trie


def findPrefixes(trie, word):
    results = {}
    current = trie

    for length, l in enumerate(word, start=1):
        if l in current:
            current = current[l]
        else:
            break
        if current.get('isWord'):
            results[current['isWord']] = length

    return results


def find_num_spaces(big_string, small_strings):
    trie = buildTrie(small_strings)
    N = len(big_string)

    def helper(index=0):
        nonlocal trie, N

        if index == N:
            return 0

        prefixes = findPrefixes(trie, big_string[index:])

        if prefixes:
            return min(1 + helper(index + length) for length in prefixes.values())
        else:
            return float('inf')

    return helper() - 1


big_string = '3141592653589793238462643383279'
small_strings = ['3', '314', '49', '9001', '15926535897', '14', '9323', '8462643383279', '4', '793', '3141592653589793238462643383278', '314159265358979', '3238462643383279']

assert find_num_spaces(big_string, small_strings) == 1

big_string = '3141592653589793238462643383279'
small_strings = ['3', '314', '49', '9001', '15926535897', '14', '9323', '8462643383279', '4', '793', '3141592653589793238462643383278', '3141592', '65358979323']

assert find_num_spaces(big_string, small_strings) == 2

Since we do our preprocessing in the form of a trie, we know how to efficiently reconstruct our big_string. The general idea here is that we are trading space for time complexity. Storing our strings allows for efficient exploration of the problem space.

Note: I assumed you only needed the number of spaces required-- requiring the specific strings involved would tweak this solution slightly. There would be an additional variable that would track the working solution through the recursion.