Given multiple path templates, how can I merge them into a single complete one

Probably not the most optimized way of doing this but I ended up associating weights on path sections. Starting with the shortest url, I detect new sections and removed sections that I then assume are arguments. On the shortest path I use increments of 10 to leave space which I assume is reasonable. The diff method simply returns the difference between 2 lists. I also use a third element in the tuple indicating if the argument is optional, allowing me to add a '?' in the template. The code isn't clean but it works rather well:

shortest_string = reduce(lambda a, b: a if len(a) <= len(b) else b, paths)
paths.remove(shortest_string)

shortest = [e for e in shortest_string.split('/') if len(e) > 0]
weighted = [((i + 1) * 10, v, False) for i, v in enumerate(shortest)]

for p in paths:
    psplit = [e for e in p.split('/') if len(e) > 0]
    new_elements = diff(psplit, shortest)
    removed_elements = diff(shortest, psplit)

    for w in weighted:
        if w[1] in removed_elements:
            w[2] = True
        if w[1] in psplit:
            i = psplit.index(w[1])
            psplit[i] = w
    for i, ps in enumerate(psplit):
        if i < len(psplit) - 2 and isinstance(psplit[i + 1], tuple) and not isinstance(ps, tuple):
            psplit[i] = (psplit[i + 1][0] - 1, ps, ps in new_elements)
            weighted.append(psplit[i])
        elif not isinstance(ps, tuple):
            psplit[i] = (psplit[i - 1][0] + 1, ps, ps in new_elements)
            weighted.append(psplit[i])

template = '/'.join(['{' + (e[1][1:-1].split(':')[1] if e[1].startswith('<') else e[1]) + ('?' if e[2] else '') + '}'
                 if e[2] or e[1].startswith('<') else e[1] for e in sorted(weighted, key=lambda x: x[0])[1:]])

If you have all the paths in a python list, you start by selecting the shortest path because the shortest path would be the one where all optional parameters are missing (in the example: "/client/get")

Then, you look through the list for optional parameter additions at the start or end of the url using some sort of pattern matching like RegExp

import re

# holds smallest possible url
shortest = '/client/get'

# holds the url template you want
template = '/client/get'

# iterates through URLs
for poss_url in url_list:

     # Checks beginning of URL
     match = re.search('w+' + shortest, poss_url)
     if match is not None:
          string = match.group()
          string = string[1:]
          string = string[:-len(shortest)]
          template = '/{' + string + '}' + template

     # Checks end of URL
     match = re.search(shortest + 'w+', poss_url)
     if match is not None:
          string = match.group()
          string = string[1:]
          string = string[:-len(shortest)]
          template = template + '{' + string + '}'