Member Avatar for snow56border

I am working on an assignment in python. The goal is to make a function with two parameters, one for a string and the other for a pattern. If the pattern appears in the string, the program must return true, or false if otherwise. Also, the pattern can accept *'s to represent any number of characters can appear in between and the pattern is still good.
ex.
matchPat(a*t*r. anteaters)
True
matchPat(a*t*r. albatross)
Ture
matchPat(a*t*r. albatross)
False

I have the function set to look through the string one at a time for a match with the first character of the pattern. If true it dumps that character and letters in the string it looked for.

It goes through good enough, but once I get to the end I get an index error since I am usually passes pattern in as "" which isnt allowed. Problem is when I block that instance all I get for an output is None and not true which is what I need.

I put some print statements up and noticed when I get to the end of pattern and the end of the string, I get a random burp of previous values, so I am guessing something in my recursion is off. Any pointers pros? Oh, and no uses of loops

def matchPat(CH, string):
    print(CH)
    print(string)
    input("")
    if not CH:
        return True
    elif CH[0] == string[0]:
        return matchPat(CH[1:], string[1:])
    elif CH[1] == string[0] or matchPat(CH, string[1:]):
        matchPat(CH[1:], string)
        print(CH)
        print(string)

print(matchPat("a*t*r","anteater"))
  • 5 Contributors
  • 5 Replies
  • 393 Views
  • 1 Week Discussion Span
  • Latest Post Latest Post by TrustyTony

Dani AI

Generated

A few concrete points from the thread before a compact, loop-free solution.

is right about the index error and the missing return — always check lengths before accessing CH[1], and if you call the matcher recursively you must return its result. gave a correct working pattern but used any()/a loop and asked for a no-loop/no-any version. Below is a purely recursive, loop-free function that implements * as "zero or more characters" and avoids the index errors you were hitting.

def match_recursive(pat, s):
    # pat: pattern string ( '*' is the wildcard )
    # s: input string to test
    if not pat:
        return not s
    if pat[0] != '*':
        # need a character in s and it must match
        return bool(s) and pat[0] == s[0] and match_recursive(pat[1:], s[1:])
    # pat starts with '*'
    # choice 1: '*' matches zero chars
    if match_recursive(pat[1:], s):
        return True
    # choice 2: '*' consumes one char (if available) and we try again
    if s and match_recursive(pat, s[1:]):
        return True
    return False

Notes and quick tips:

  • Base cases: empty pattern only succeeds on empty string. The '*' branch tries zero characters first (important to allow trailing * to match empty string) and then consumes one character at a time by recurring on the same pattern. This avoids loops/any().
  • Performance: this plain recursion can be exponential on long inputs. To make it practical, memoize (e.g., with functools.lru_cache) or implement an iterative DP using indices rather than slicing. If you must support very long strings, use a DP or the regex module as suggested.

Recommended Answers

All 5 Replies

Member Avatar for griswolf

You want to use the re nodule. There are examples of use as well as a full reference. Be aware of the difference between the search and the match methods.

Member Avatar for woooee

You have to test for a length of 2 or greater, otherwise you get and index error on the [1:]s.

return matchPat(CH[1:], string[1:])
    elif CH[1] == string[0] or matchPat(CH, string[1:]):

Note also that line 10
matchPat(CH[1:], string)
does not catch the return from the matchPat function so the "return True" is never caught. Add some print statements so you can see what is happening with each recursion.

Edited by woooee because: n/a
Member Avatar for TrustyTony

This my try seems to work, I do not know if I am overcomplicating things, but you could compare this to your try and maybe debug the problem:

from __future__ import print_function

def match_pat(CH, mystring):
    print ("%r vs %r" % (CH, mystring))
    if not CH:
        return not mystring
    elif CH == '*':
        return True
    elif not mystring:
        return False
    elif CH[0] == '*':
        return any(match_pat(CH[1:],mystring[index:]) for index in range(len(mystring)))
    else:
        return CH[0] == mystring[0] and match_pat(CH[1:], mystring[1:]) 

pat = 'a*at*r*' 
for word in ("anteater",'albatross','albania'):
    print(word, pat, match_pat(pat,word))
    print('-'*30)
Edited by TrustyTony because: more PEP8
Member Avatar for xhaui

This my try seems to work, I do not know if I am overcomplicating things, but you could compare this to your try and maybe debug the problem:

from __future__ import print_function

def match_pat(CH, mystring):
    print ("%r vs %r" % (CH, mystring))
    if not CH:
        return not mystring
    elif CH == '*':
        return True
    elif not mystring:
        return False
    elif CH[0] == '*':
        return any(match_pat(CH[1:],mystring[index:]) for index in range(len(mystring)))
    else:
        return CH[0] == mystring[0] and match_pat(CH[1:], mystring[1:]) 

pat = 'a*at*r*' 
for word in ("anteater",'albatross','albania'):
    print(word, pat, match_pat(pat,word))
    print('-'*30)

This code is great and works fine. The only problem is with line 12 I believe it is where you say:

return any(match_pat(CH[1:],mystring[index:]) for index in range(len(mystring)))

Is there any way to change this line so it doesn't use a for loop or the any operator? Both of these are not allowed in the final submission.

Member Avatar for TrustyTony

You could replace the loop part by appropriate recursion. That is appropriate home work for you to understand how.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.