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