papasmurf papasmurf - 17 days ago 6
Python Question

Search a string for a given key

I've been doing some more

CodeEval
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:
Hello,ell
your job is to figure out if
ell
is in
hello
, 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")
true
>>> search_string("testing", "rawr")
false"""
results = []
for c in string:
for ch in key:
if c == ch:
results.append(c)
if len(string) / 2 < len(results) or len(string) / 2 == len(results):
return "true"
else:
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

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
    #print(key)

    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"
            break

    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