The script computes the minimum number of partitions of input string with respect to a given list of strings, if exists. Refer: https://youtu.be/tOD6g7rF7NA?t=268

find_minimum_number_partitions.py

input_string = "31495"
fav_strings = ["31", "314", "3149", "495"]
INF = len(input_string)


def substring_match(pos):
    match_lengths = []
    for fav_string in fav_strings:
        if len(fav_string) + pos <= len(input_string):
            if fav_string in input_string[pos: pos + len(fav_string)]:
                match_lengths.append(len(fav_string))
            else:
                match_lengths.append(None)
        else:
            match_lengths.append(None)
    return match_lengths        


def count_min_partitions(pos):
    global input_string, fav_strings, INF
    # determine matching strings in fav array
    if (pos == len(input_string)):
        return -1
    match_lengths = substring_match(pos)
    # if no matching string , return None
    min_count = INF
    min_string_id = -1
    # for each match 
    for id in range(len(fav_strings)):
        if match_lengths[id] is None: # match not found
            count = INF
        else: # match found
            count = 1 + count_min_partitions(pos + match_lengths[id])
            if (count < min_count):
                min_string_id = id
            min_count = min(count, min_count) # update the minimum
    return min_count        
        

def main():
    solution = count_min_partitions(0)
    print("Min spaces: ",  solution if (solution < INF) else "No solution")
    
if __name__ == '__main__':

    main()