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 not matches:
matches = dict()
if not pattern and not string:
return True
if pattern:
head = pattern[0]
else:
return False
expect = matches.get(head)
if expect:
if string.startswith(expect):
return search(pattern[1:], string[len(expect):], matches)
else:
return False
else:
for matchLen in range(len(string),0,-1): # loop from len(string) to 1
match = string[:matchLen]
matches[head] = match
if search(pattern[1:], string[len(match):], matches):
return True
else:
del matches[head]
else:
return False
print (search("abab","cat" + "dog" + "cat" + "dog"))
print (search("aba","cat" + "dog" + "cat"))
print (search("abba","cat" + "dog" + "dog" + "cat"))
print (search("abcac","cat" + "dog" + "mouse" + "cat" + "mouse"))
print (search("abcde","efghi"))
print (search("a","efghi"))
print ("---")
print (search("abab","cat" + "dog" + "cat" + "cat"))
print (search("abab","cat" + "dog" + "cat" + "dogg"))
print (search("abab","cat" + "do" + "cat" + "dog"))
print (search("abab","cat" + "dog" + "cat"))
print (search("abcdefghi","cat"))
print (search("abba","red" + "blue" + "red" + "blue"))
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.