4 ms·
Please show me a regex parser in 18 lines of code! Even 36! I did this exercise once and it took 100s of lines, I think using C++... but it's been a long time
by epicureanideal 8y ago
Please show me a regex parser in 18 lines of code! Even 36! I did this exercise once and it took 100s of lines, I think using C++... but it's been a long time. Maybe it's significantly shorter in Python? But still 18 lines is impressive.
- psurge 8y agoI probably screwed something up, but here's a 16 line attempt in Python, where the regex specials are limited to .?: def matches(pattern, s): if len(pattern) == 0: return True c = pattern[0] assert c not in ("*", "?") if len(pattern) > 1: if pattern[1] == "?": return ( len(s) > 0 and c in (".", s[0]) and matches(pattern[2:], s[1:]) ) or matches(pattern[2:], s) elif pattern[1] == "*": for i, d in enumerate(s): if c not in (".", d): break return any(matches(pattern[2:], s[j:]) for j in range(i, -1, -1)) return len(s) > 0 and c in (".", s[0])
- m0zg 8y agoPretty much something along these lines, except it's also required that both pattern and s end at the same time for a full match (this complicates the base case a tiny bit). The C/C++ solution looks more elegant because you can use pointers. Note that this particular version requires no prior knowledge of the algorithm and can be solved on the spot fairly easily.
- epicureanideal 8y agoThanks for the demonstration!
- Kephael 8y agoThis is LeetCode #10, this is a common question.