How do I find a substring in a string using recursion only?-CodePudding

So here is my code

def count_occurrences(sub, s):

    if len(s) == 0:
        return 0
    
    else:
        if str(sub) in str(s) and str(sub) == str(s):
            return 1 count_occurrences(sub, s[1:])     
        else:
            return count_occurrences(sub, s[1:])
        
print(count_occurrences('ill', 'Bill will still get ill'))

I believe this if str(sub) in str(s) and str(sub) == str(s): statement is throwing me off when I run the debugger UI. If I just put if str(sub) in str(s) it gives me a number but it is not the number I want which is 4.

CodePudding user response：

Your code didn't quite work properly because you skipped one character only if you found the substring that will lead the program to find the substring at the same place, instead you have to skip to the index after the first occurence of the substring. This code will work

def count_occurences(s, sub):
    if len(s) == 0:
        return 0
    else:
        ind = s.find(sub)

        if ind>=0:
            return 1 count_occurences(s[ind 1:], sub)
        else:
            return 0

I added 1 to the index because, in the case of "ill", find() will give me the index of the letter 'i', so if I give s[ind 1:] that will remove all the characters before the first 'l' i.e including 'i', so the next iteration won't find "ill" in the same place as before which leads to counting the same occurence twice.

CodePudding user response：

your condition str(sub) == str(s) will never be True, except maybe if the substring is at the very end. You have to compare the start of the string (same length as the substring) instead of searching for it at any position, otherwise you'll count the same match multiple times. Also, you dont need to use str() if you are already processing strings.

def count_occurrences(sub, s):
    if len(sub)>len(s): return 0
    return s.startswith(sub)   count_occurrences(sub,s[1:]) # True is 1

Output:

print(count_occurrences('ill', 'Bill will still get ill'))

4

Note that I assumed that you want to count overlapping substrings. For example: 'ana' counts for 2 in 'banana'.

CodePudding user response：

You can use str.split() and use .count() for counting like below:

def count_occurrences(sub, s):
    if not(len(s.strip())):
        return 0
    splt_s = s.split()
    return (splt_s[0].count(sub))   count_occurrences(sub, ' '.join(splt_s[1:]))

Output:

>>> count_occurrences('ill', 'Bill will still get ill')
4

>>> count_occurrences('ill', 'Billwillstillgetill   Billwillstillgetill    ')
8