After a little preparation with string.maketrans, strings' translate method affords very fast and simple operation. I'm giving Python 2 code for plain strings (Python 3, and Unicode strings in Python 2, are a bit different -- ask if that's what you need):
The preparation (do once and for all, e.g. at module load time):
>>> import string
>>> allchars = string.maketrans('', '')
>>> nondigits = allchars.translate(allchars, string.digits)
The execution (turn any suitable string into the property formatted number):
>>> x='1555-555-5555'
>>> y=(x.translate(allchars, nondigits)).lstrip('1')
>>> assert len(y) == 10
>>> '%s-%s-%s' % (y[:3], y[3:6], y[6:])
'555-555-5555
Of course, you'll need to decide what to do when len(y) does not equal 10 (just raise an exception as I'm doing here, or, what else). But, this would be needed for any other form of processing (regex or whatever) just as well. The translate approach is really really fast and simple!-)