Multi-replacement in a string, independently and prioritized

Question

I need a shorter way to do this.

• input: an ordered list of string pairs L; and a string s

• task: for each pair (a,b), replace each occurrence a in s by b

• note 1: the replacements have to be independent. The result of one replacement can not be taken as a trigger for a subsequent replacement

  Example: L=(("a","b"),("b","c")); s="ab"; desired output: "bc", and not "cc".

• note 2: L is ordered; the beginning of the list has higher priority, so if L is (("xyz", "P"), ("xy", Q)) and s is "wxyzabc" then the result should be "wPabc". If the order of L were reversed, the result would be "wQzabc".

• bonus: it's a great thing if it can also handle regex patterns as replacement pairs

My idea:

• iterate over L, and replace each source to a sequence of joker characters of equal length (the joker does not appear anywhere in the string), while noting the position where we found it.
• then split the string to a list of strings of length 1, replace the first joker of each sequence with the desired target replacement, join the list back together and remove jokers.

Here is my implementation in Python:

def multireplace(text, changes):
    # find a possible joker character
    for num in range(256):
        joker = chr(num)
        if text.find(joker) != -1:
            continue

        jokerUsable = True
        for old,new in changes:
            if old.find(joker) != -1 or new.find(joker) != -1:
                jokerUsable = False
                break

        if jokerUsable:
            break

    # list of lists, each list is about one replacement pair, 
    # and its elements will be the indices where they have to be done
    index_lists=[]
    
    for old, new in changes:
        indices = []
        pattern = re.escape(old)
        for m in re.finditer(pattern, text):
            indices.append(m.start())

        text = text.replace(old, joker*len(old))
        index_lists.append(indices)

    character_list = list(text)
    for i in range(len(index_lists)):
        old, new = changes[i]
        for place in index_lists[i]:
            character_list[place] = new

    # remove jokers
    i=0
    while i < len(character_list):
        if character_list[i] == joker:
            del character_list[i]
        else:
            i+=1

    return "".join(character_list)

This is very cumbersome, and seems to be a standard problem, so I was wondering if there is a standard way of doing this.

Answer 1

Do it recursively. Split the string by the first "from" value, recurse with the rest of the changes for each resulting part, then join them back together with the "to" value.

def multireplace(text, changes):
    if not changes:
        return text

    from_, to = changes[0]
    parts = text.split(from_)
    return to.join((multireplace(part, changes[1:]) for part in parts))

• Advantage: Short and clean code
• Disadvantage: Uses linear stack with respect to the number of changes. Might lead to stack overflow in case of lots of replacement pairs.

(Note: this answer is based on an earlier answer that somehow got deleted)

Answer 2

If you can be fairly certain they won't appear in the string generally, just use standard str.format templates:

def multireplace(text, changes):
    replacements = []
    for index, change in enumerate(changes):
        frm, to = change
        text = text.replace(frm, "{{{0:d}}}".format(index))
        replacements.append(to)
    return text.format(*replacements)

Answer 3

Go recursive:scan the list until a match is found. Split string by the match. Apply (recursively) the rest of the list to all substrings generated by split. Join back with a substitution, and return.

Sorry can't give an example on my phone...