|
|
|
|
|
|
by generallyfalse
2893 days ago
|
|
|
This is what I tried, recursion taking care of puting the simplest cases first. I haven't checked the solution. I think this kind of problem is like a state machine. In each call of the recursion the length of the pattern or the lengh of the string should decrease, so finally one get to the easy cases of length in (0,1,2). This kind of problems are designed to test you can define a grammar and apply recursion. Another problem with the same flavor could be to evaluate string expressions like "3+25" using a grammar. My one-hour solution (not checked). But I think I have done similar problems. def pat(s,p):
...: if s == "":
...: if len(p)>1 and p[1] in "?*":
...: return pat(s,p[2:])
...: if p == "": return s == p
...: if len(p) == 1:
...: if p == "*": return True
...: return s == p
...: if len(p) == 2:
...: if p[1] == "?":
...: return s == p[0] or s==""
...: if p[1] == "*":
...: if s[0] != p[0]: return False
...: if s == p[0]: return True
...: return pat(s[1:],p)
...: if p[1] != "?" and p[1] != "*":
...: return s[0] == p[0] and pat(s[1:],p[1:])
...: if p[1] == "?":
...: if (s[0] != p[0]):
...: return pat(s,p[2:]))
...: if (s[0] == p[0]):
...: return pat(s[1:],p[2:]) or pat(s,p[2:])
...: if p[1] =="*":
...: if (s[0] != p[0]): return pat(s,p[2:])
...: return pat(s[1:],p) or pat(s,p[2:])
...:
...:
|
|
|