3 ms·
It's fun to think of the regular expression which matches all strings off by Levenshtein=1. For "hello" it's something like: hello|ello|hllo|helo|hell|.hello|h
by jhallenworld 11y ago
It's fun to think of the regular expression which matches all strings off by Levenshtein=1. For "hello" it's something like: hello|ello|hllo|helo|hell|.hello|h.ello|he.llo|hel.lo|hell.o|hello.|.ello|h.llo|he.lo|hel.o|hell.
This seems pretty easy to generate the NFA for this, then compile it to a DFA as usual.
- TheLoneWolfling 11y agoThe problem with this approach is that it can be (absurdly) complex to generate, even when the actual DFA output required is small. Look at the intermediates generated by something like "hhhhh". There is a massive amount of redundancy there.
- fenollp 11y agoOr: hello|.?ello|h.?llo|he.?lo|hel.?o|hell.?
- cousin_it 11y agoThat doesn't match "helloo".