Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#!/usr/bin/env python3
def search(pattern, string, matches=None):
if matches is None: matches = dict()
maxMatchLen = len(string)
while(maxMatchLen != 0):
match = string[0:maxMatchLen]
head = pattern[0]
matchesCopy = dict(matches)
if head not in matchesCopy:
matchesCopy[head] = match
if matchesCopy[head] == match:
if len(pattern) > 1:
tail = pattern[1:]
remainingString = string[len(match):]
if (len(remainingString) > 0
and search(tail, remainingString, matchesCopy)):
return True
else:
# We've implicitly checked the desired pattern is matched
if len(string[len(match):]) == 0:
return True
maxMatchLen -= 1
return False
def test(pattern, string, expect):
print("ok") if (search(pattern, string) == expect) else print("nok")
test(["a", "b", "a", "b"], "redblueredblue", True)
test(["a", "b", "b", "a"], "catdogdogcat", True)
test(["a", "b", "a", "b"], "redblueredblue", True)
test(["a", "b", "a", "b"], "cat" + "dog" + "cat" + "dog", True)
test(["a", "b", "a"],"cat" + "dog" + "cat", True)
test(["a", "b", "b", "a"],"cat" + "dog" + "dog" + "cat", True)
test(["a", "b", "c", "a", "c"],"cat" + "dog" + "mouse" + "cat" + "mouse", True)
test(["a", "b", "c", "d", "e"],"efghi", True)
test(["a"],"efghi", True)
test(["a", "b", "a", "b"],"cat" + "dog" + "cat" + "cat", False)
test(["a", "b", "a", "b"],"cat" + "dog" + "cat" + "dogg", False)
test(["a", "b", "a", "b"],"cat" + "do" + "cat" + "dog", False)
test(["a", "b", "a", "b"],"cat" + "dog" + "cat", False)
test(["a", "b", "c", "d", "e", "f", "g", "h", "i"],"cat", False)
test(["a", "b", "b", "a"],"red" + "blue" + "red" + "blue", False)
test(["a", "b", "a"], "patrpatrr", False)
@ZtianWisc

This comment has been minimized.

Copy link

ZtianWisc commented May 15, 2018

pattern 'abba'
string 'redredredred'
should return false, but your solution return true.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.