Sort 28 Discussions, By:
Please Login in order to post a comment
Wow, this was the hardest problem in the Strings section so far. I'm surprised it is not marked as Expert.
Ok, thanks for a pretty epic problem! But what about the exponential blowup of the number of states? I bet this testcase will prove to be problematic for most of the solutions ;)
It took me 2 days to learn about regex, NFA, DFA, and Thompson and subset construction and also 400 lines of code to accomplish this exercise :) I also think there is a somewhat simpler solution. You can use NFA construction right fron regex string like it is done here: http://algs4.cs.princeton.edu/54regexp/NFA.java.html. And then construct DFA from it without parsing regex to tree and then converting tree to NFA. Or even construct NFA without eps-transitions right fron the string. But it's quite convoluted I think.
In order to solve it you have to read this:
You have to address the following:
regex to nfa, nfa to dfa, minimize dfa, matrix exponentiation
Although I liked this problem, |S|<100 was really a stab in the back. Who could even think that they specially filtered out test-cases which cause exponential growth of number of states.