10. Regular Expression Matching

The is the whole difficulty: it binds to the previous character and can mean zero, one, or many repeats. That branching is why a greedy left-to-right scan can't work — you don't know up front how…