5
\$\begingroup\$

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]
  1. 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)
  1. 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)
  1. Bind the matches with their lengths in a dictionary
sizes = dict()
for tup in matches:
  sizes[tup] = len(tup)
  1. Finding the optimal solution (minimal length and where it occurres)
min_key = min(sizes, key=sizes.get)
min_val = sizes[min_key]
  1. 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.

\$\endgroup\$
3
  • \$\begingroup\$ Welcome to CodeReview@SE. \$\endgroup\$
    – greybeard
    Dec 26, 2019 at 7:06
  • \$\begingroup\$ (It is unusual for questions here to present code "from a single source code file" as separate snippets. I am not sure I like it - can you provide a hyperlink to some code repository so reviewers can get an overall view without pasting snippets themselves?) \$\endgroup\$
    – greybeard
    Dec 26, 2019 at 7:08
  • \$\begingroup\$ Just added a link to the project, directly in repl, where you can test it. Here it is: repl.it/@LucasWerner/String-Least-Spacing \$\endgroup\$ Dec 26, 2019 at 15:33

1 Answer 1

2
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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