Code that is able to search for a string in a text recursively

I have a code which satisfies the question above. However, I am personally curious on how to recode it such that if the text did not have a space and is given as "LoveIsWar", the code will still return true if the string is "War".

However, I thought of doing a check for letter by letter but I am unsure how to do it. Would really appreciate if I could get guidance on this!

def find(text, substring):
    if(len(text) <= 0):
        return None
    elif(text[0] == substring):
        return substring
    else:
        return find(text[1:], substring)


def is_string_there(text, string):
    if find(text.split(), string):
        return True
    else: return False

print(is_string_there("love is war","war"))
print(is_string_there("love is war","warfalse"))

This is the edited code that satisfies everything I want. Being able to check for the string if the text has spaces or not even if the string has capital letters in it.

def find(text, substring):
    if(len(text) <= 0):
        return None
    elif(text[0:len(substring)] == substring):
        return substring
    else:
        return find(text[1:], substring)


def is_string_there(text, string):
    if find(text.lower(), string.lower()):
        return True
    else: return False

print(is_string_there("love is war","war"))
print(is_string_there("love is war","warfalse"))

Answer

Great question. Given the constraint of a recursive function, in layman’s terms, what you want to achieve is a sliding-window search on a string.

That is to say, that when you pass your ‘text’ into the find function, you do not pass it as an array, you pass the text itself.

The ‘find’ function then doesn’t iterate through the elements in the ‘array’, but through the letters in the string, discarding them one by one. Hence, your “window” – or your view on the string, slides across it until you finish.

All you really need to modify is:

text[0] == substring

Should check if the text[0:length_of_substring] matches the substring. Remember, we have much the same operations on strings as we do on arrays!

If it does not, move 1 character along (much like you do in your array-based search).

For your interest, these kinds of problems can be solved very efficiently using algorithms such as Rabin Karp

A small optimisation you could make is breaking out of your search when you have fewer characters left in your “text” than there are in your substring.

Hope that helps!