Skip to content

Instantly share code, notes, and snippets.

@busser
Created January 24, 2019 20:51
Show Gist options
  • Save busser/fb96d8a1c5f64e336885364cb46d0e88 to your computer and use it in GitHub Desktop.
Save busser/fb96d8a1c5f64e336885364cb46d0e88 to your computer and use it in GitHub Desktop.
#!/usr/bin/env python3
"""
Write a function that takes two strings as arguments, s and p,
and returns a boolean denoting whether s matches p.
p is a sequence of any number of the following:
1. a-z - which stands for itself
2. . - which matches any character
3. * - which matches 0 or more occurences of the previous single character
s = "aba", p = "ab" -> false
s = "aa", p = "a*" -> true
s = "ab", p = ".*" -> true
s = "ab", p = "." -> false
s = "aab", p = "c*a*b" -> true
s = "aaa", p = "a*." -> true
"""
def is_match(s: str, p: str) -> bool:
"""Checks whether s matches p.
Here, p is a sequence of any number of the following:
1. a-z - which stands for itself
2. . - which matches any character
3. * - which matches 0 or more occurences of the previous single character
Args:
s: any string
p: a regex-like pattern
Returns:
A boolean denoting whether s matches p.
"""
# pattern and string both empty: match
if len(s) == 0 and len(p) == 0:
return True
# pattern empty but not string: no match
if len(p) == 0:
return False
# 0+ occurences:
if len(p) >= 2 and p[1] == '*':
# string empty but not pattern
if len(s) == 0:
return is_match(s, p[2:])
# is_match(s, p[2:]): 0 occurences
# is_match(s[1:], p): 1+ occurence
return is_match(s, p[2:]) or is_match(s[1:], p)
# string empty but not pattern: no match
# (all following checks require 1+ characters in string)
if len(s) == 0:
return False
# any character
if p[0] == '.':
return is_match(s[1:], p[1:])
# specific character
if s[0] == p[0]:
return is_match(s[1:], p[1:])
return False
def _test_is_match() -> None:
assert(is_match('aba', 'ab') == False)
assert(is_match('aa', 'a*') == True)
assert(is_match('ab', '.*') == True)
assert(is_match('ab', '.') == False)
assert(is_match('aab', 'c*a*b') == True)
assert(is_match('aaa', 'a*a') == True)
def main():
_test_is_match()
print('The is_match function passed all tests.')
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment