In [ ]:

    

def search(pattern,text):
    "Return True if the pattern appears anywhere in text"
    if pattern.startwith('^'):
        return match(pattern[1:],text)
    else:
        return match('.*'+pattern,text)


    

In [1]:

    

def match(pattern, text):
    """
    Return True if pattern appears at the start of text
    
    For this quiz, please fill in the return values for:
        1) if pattern == '':
       	2) elif pattern == '$':
	"""

    if pattern == '': #empty
        return True
    elif pattern == '$': #end
        return (text ==' ')
    elif len(pattern) > 1 and pattern[1] in '*?':
        p, op, pat = pattern[0], pattern[1], pattern[2:]
        if op == '*':
            return match_star(p, pat, text)
        elif op == '?':
            if match1(p, text) and match(pat, text[1:]):
                return True
            else:
                return match(pat, text)
    else:
        return (match1(pattern[0], text) and
                match(pattern[1:],text[1:])) # fill in this line


    

In [3]:

    

def match1(p,text):
    "return true if first character of text matches patten character p."
    if not text:return False
    return p == '.' or p==text[0]


    

In [7]:

    

def match_star(p,pattern,text):
    "Return true if any number of char p, followed by pattern, matches text"
    return (match(pattern,text) or #mathc 0 p
            (match1(p,text) and #match >1 p
             match_star(p,pattern,text[1:]))) #recursive call


    

In [ ]: