So, the community, I ask you to give me a chance to surprise you the third time, I used the python in the previous decision, I thought I would draw the attention of experts and they will immediately tell me, but why do it, do I have regular expressions - I did everything there will work, this our python can give and more speed.

The next topic of the article should be another task in turn, but no, I did not leave the first one, which can be done to get an even faster solution, since the victory on the site was crowned with another contest.

I wrote an implementation which on average was of this kind of speed, so there are 90 percent of the solutions that I did not notice that someone knows how to solve it even faster and he is silent , and having looked at the two previous articles did not say: oh, if this a performance question, then everything is clear - the prologue does not fit here. But with performance now everything is fine, imagine a program that will run on a weak gland is not possible, "in the end, why think about it?"

Call

Solve the problem even faster, was there a python and there was time, and is there a faster solution on python?

I’m told "Runtime: 2504 ms, faster than 1.55% of Python3 online submissions for Wildcard Matching."

I warn you, there is a stream of thoughts online.

1 regular?

Maybe there is an option to write a faster program simply by using a regular expression.

Explicitly python can create a regular expression object that will check the input string and it will turn out to run right there, in the sandbox that is on the site for testing programs.
Just import re , I can make the import of such a module, it is interesting, we must try.

It is not easy to understand that creating a quick solution is not easy. We'll have to search a little, try and create an implementation like this:

1. make the object of this regular season,
2. slip the pattern corrected by the rules of the chosen library to it,
3. compare and answer is ready
Voila:

import re def isMatch(s,p): return re.match(s,pat_format(p))!=None def pat_format(pat): res="" for ch in pat: if ch=='*':res+="(.)*" if ch=='?':res+="." else: res+=ch return res 

Here is a very short decision, as if correct.

I try to run it, but it was not there, it was not quite right, some option does not fit, it is necessary to test the conversion to a template.

The truth is funny, I confused the pattern and the string, and the solutions came together, I passed 1058 tests and failed, only here.

Once again, on this site they are working carefully on the tests, as it turned out, all the previous ones are good, but here two main parameters are mixed up and this is manifested, here are the advantages of TDD ...

And on such a wonderful text, I still get an error

 import re def isMatch(s,p): return re.match(pat_format(p),s)==None def pat_format(pat): res="" for ch in pat: if ch=='*':res+="(.)*" else: if ch=='?':res+="." else:res+=ch return res 

Complicated

It looks like this task was specially overlaid with tests, so that those who want to use regular expressions get more difficulties, I didn’t have any logical errors in the program before, and there are so many things to consider.

So, the regular expression matches and the first result should be equal to our string.

Victory?
It wasn’t easy to force him to use a regular expression, but the attempt failed, it’s not a simple solution to chemize regulars. The solution to the search in width worked faster.

This is the implementation

 import re def isMatch(s,p): res=re.match(pat_format(p),s) if res is None: return False else: return res.group(0)==s def pat_format(pat): res="" for ch in pat: if ch=='*':res+="(.)*" else: if ch=='?':res+="." else:res+=ch return res 

leads to this:

Appeal

Dear residents, try to check this out here, and Python makes it three , it cannot quickly accomplish this task:

 import re def isMatch(s,p): res=re.match(pat_format(p),s) if res is None: return False else: return res[0]==s def pat_format(pat): res="" for ch in pat: if ch=='*':res+="(.)*" else: if ch=='?':res+="." else:res+=ch return res ##test 940 import time pt=time.time() print(isMatch("aaaabaaaabbbbaabbbaabbaababbabbaaaababaaabbbbbbaabbbabababbaaabaabaaaaaabbaabbbbaababbababaabbbaababbbba","*****b*aba***babaa*bbaba***a*aaba*b*aa**a*b**ba***a*a*")) print(time.time()-pt) 

You can try at home. Miracles, it is not just long solved, it hangs, oooh.

Regular expressions as a subset of the declarative look limp performance?
The statement is strange, they are also present in all fashionable languages, does the performance have to be, but it’s not at all real that there’s not a finite state machine there ?, what happens in an endless cycle ??

Go

I read in one book, but it was a long time ago ... the newest language, Guo, works very quickly, but what about the regular expression?

I try and him:

 func isMatch(s string, p string) bool { res:=strings.Replace(p, "*", "(.)*", -1) res2:=strings.Replace(res, "?", ".", -1) r, _ := regexp.Compile(res2) fr:=r.FindAllString(s,1) return !(len(fr)==0 || len(fr)!=0 && fr[0]!=s) } 

I admit, it was not easy to get such a concise text, the syntax there is not trivial, even with the knowledge of C, it's not easy to understand ...

This is a remarkable result, the speed really goes off scale, for a total of ~ 60 milliseconds, but surprisingly, this solution is faster than only 15% of the answers on the same site.

Where's the prologue

I find that this forgotten language for working with regular expressions provides us with a Perl Compatible Regular Expression library .

This is how it can be implemented, but pre-process the template string with a separate predicate.

 pat([],[]). pat(['*'|T],['.*'|Tpat]):-pat(T,Tpat),!. pat(['?'|T],['.'|Tpat]):-pat(T,Tpat),!. pat([Ch|T],[Ch|Tpat]):-pat(T,Tpat). isMatch(S,P):- atom_chars(P,Pstr),pat(Pstr,PatStr),!, atomics_to_string(PatStr,Pat), term_string(S,Str), re_matchsub(Pat, Str, re_match{0:Str},[bol(true),anchored(true)]). 

And the lead time is excellent:

 isMatch(aa,a)->ok:0.08794403076171875/sec isMatch(aa,*)->ok:0.0/sec isMatch(cb,?a)->ok:0.0/sec isMatch(adceb,*a*b)->ok:0.0/sec isMatch(acdcb,a*c?b)->ok:0.0/sec isMatch(aab,c*a*b)->ok:0.0/sec isMatch(mississippi,m??*ss*?i*pi)->ok:0.0/sec isMatch(abefcdgiescdfimde,ab*cd?i*de)->ok:0.0/sec isMatch(zacabz,*a?b*)->ok:0.0/sec isMatch(leetcode,*e*t?d*)->ok:0.0009980201721191406/sec isMatch(aaaa,***a)->ok:0.0/sec isMatch(b,*?*?*)->ok:0.0/sec isMatch(aaabababaaabaababbbaaaabbbbbbabbbbabbbabbaabbababab,*ab***ba**b*b*aaab*b)->ok:0.26383304595947266/sec isMatch(abbbbbbbaabbabaabaa,*****a*ab)->ok:0.0009961128234863281/sec isMatch(babaaababaabababbbbbbaabaabbabababbaababbaaabbbaaab,***bba**a*bbba**aab**b)->ok:0.20287489891052246/sec 

BUT, there are some restrictions, another test brought:

 Not enough resources: match_limit Goal (directive) failed: user:assert_are_equal(isMatch(aaaabaaaabbbbaabbbaabbaababbabbaaaababaaabbbbbbaabbbabababbaaabaabaaaaaabbaabbbbaababbababaabbbaababbbba,'*****b*aba***babaa*bbaba***a*aaba*b*aa**a*b**ba***a*a*'),false) 

As a conclusion

Total only questions left. You can realize everything, but speed is lame.
Transparent solutions are not effective?

Someone implemented declarative regular expressions, what mechanisms are there?

And how do you call such challenges, there is a task that can be solved, and where is it the perfect solution?