papasmurf papasmurf - 1 year ago 44
Python Question

Search a string for a given key

I've been doing some more

challenges and came across one on the hard tab.

You are given two strings. Determine if the second string is a substring of the first (Do NOT use any substr type library function). The second string may contain an asterisk() which should be treated as a regular expression i.e. matches zero or more characters. The asterisk can be escaped by a \ char in which case it should be interpreted as a regular '' character. To summarize: the strings can contain alphabets, numbers, * and \ characters.

So you are given two strings in a file that look something like this:
your job is to figure out if
is in
, what I do:

I haven't quite gotten it perfect, but I did get it to the point where it passes and works with a 65% complete. How it runs through the string, and the key, and checks if the characters match. If the characters match, it appends the character into a list. After this it divides the length of the string by 2 and checks if the length of the list is either greater than, or equal to half of the string. I figured half of the string length would be enough to verify if it indeed matches or not. Example of how it works:

h == e -> no
e == e -> yes -> list
l == e -> no
l == e -> no

My question is what can I do better to the point where I can verify the wildcards that are said above?

import sys

def search_string(string, key):
""" Search a string for a specified key.
If the key exists out put "true" if it doesn't output "false"
>>> search_string("test", "est")
>>> search_string("testing", "rawr")
results = []
for c in string:
for ch in key:
if c == ch:
if len(string) / 2 < len(results) or len(string) / 2 == len(results):
return "true"
return "false"

if __name__ == '__main__':
with open(sys.argv[1]) as data:
for line in data.readlines():
data_list = line.rstrip().split(",")
search_key = data_list[1]
word = data_list[0]
print(search_string(word, search_key))

Answer Source

I've come up with a solution to this problem. You've said "Do NOT use any substr type library function", I'm not sure If some of the functions I used are allowed or not, so tell me if I've broken any rules :D

Hope this helps you :)

def search_string(string, key):
    key = key.replace("\\*", "<NormalStar>") # every \* becomes <NormalStar>
    key = key.split("*") # splitting up the key makes it easier to work with

    point = 0 # for checking order, e.g. test = t*est, test != est*t
    found = "true" # default
    for k in key:
        k = k.replace("<NormalStar>", "*") # every <NormalStar> becomes *
        if k in string[point:]: # the next part of the key is after the part before
            point = string.index(k) + len(k) # move point after this
        else: # k nbt found, return false
            found = "false"

    return found

print(search_string("test", "est"))       # true
print(search_string("t....est", "t*est")) # true
print(search_string("n....est", "t*est")) # false
print(search_string("est....t", "t*est")) # false
print(search_string("anything", "*"))     # true
print(search_string("test", "t\*est"))    # false
print(search_string("t*est", "t\*est"))   # true
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download