php's strtr for python

Question

php has the strtr function:

strtr('aa-bb-cc', array('aa' => 'bbz', 'bb' => 'x', 'cc' => 'y'));
# bbz-x-y

It replaces dictionary keys in a string with corresponding values and (important) doesn't replace already replaced strings. A naive attempt to write the same in python:

def strtr(strng, replace):
    for s, r in replace.items():
        strng = strng.replace(s, r)
    return strng

strtr('aa-bb-cc', {'aa': 'bbz', 'bb': 'x', 'cc': 'y'})

returns xz-x-y which is not we want (bb got replaced again). How to change the above function so that it behaves like its php counterpart?

(I would prefer an answer without regular expressions, if possible).

Upd: some great answers here. I timed them and found that for short strings Gumbo's version appears to be the fastest, on longer strings the winner is the re solution:

# 'aa-bb-cc'
0.0258 strtr_thg
0.0274 strtr_gumbo
0.0447 strtr_kojiro
0.0701 strtr_aix

# 'aa-bb-cc'*10
0.1474 strtr_aix
0.2261 strtr_thg
0.2366 strtr_gumbo
0.3226 strtr_kojiro

My own version (which is slightly optimized Gumbo's):

def strtr(strng, replace):
    buf, i = [], 0
    while i < len(strng):
        for s, r in replace.items():
            if strng[i:len(s)+i] == s:
                buf.append(r)
                i += len(s)
                break
        else:
            buf.append(strng[i])
            i += 1
    return ''.join(buf)

Complete codes and timings: https://gist.github.com/2889181

Answer 1

The following uses regular expressions to do it:

import re

def strtr(s, repl):
  pattern = '|'.join(map(re.escape, sorted(repl, key=len, reverse=True)))
  return re.sub(pattern, lambda m: repl[m.group()], s)

print(strtr('aa-bb-cc', {'aa': 'bbz', 'bb': 'x', 'cc': 'y'}))

Like the PHP's version, this gives preference to longer matches.

Answer 2

def strtr(strng, replace):
    if replace and strng:
        s, r = replace.popitem()
        return r.join(strtr(subs, dict(replace)) for subs in strng.split(s))
    return strng

j=strtr('aa-bb-cc', {'aa': 'bbz', 'bb': 'x', 'cc': 'y'})
assert j=='bbz-x-y', j