13 ms·
I 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 le
by psurge 8y ago
I 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!