Question

I am using python. Im having trouble with this recursion problem, I am trying to find how many pairs of characters are the same in a string. For example, 'xx' would return 1 and 'xxx' would also return one because the pairs are not allowed to overlap. 'aabbb' would return 2.

I am completely stuck. I thought of breaking the word up into length 2 strings and recursing through the string like that, but then cases like 'aaa' would result in incorrect output.

Thanks.

Was it helpful?

Solution 2

You can use regex for that:

import re

s = 'yyourr ssstringg'
print len(re.findall(r'(\w)\1', s))

[OUTPUT]
4

This also takes care of your "overlaps-not-allowed" problem as you can see in the above example it prints 4 and not 5.

For a recursion approach, you can do it as:

st = 'yyourr ssstringg'

def get_double(s):
    if len(s) < 2:
        return 0
    else:
        for i,k in enumerate(s):
            if k==s[i+1]:
                return 1 + get_double(s[i+2:])

>>> print get_double(st)
4

And without a for loop:

st = 'yyourr sstringg'

def get_double(s):
    if len(s) < 2:
        return 0
    elif s[0]==s[1]:
        return 1 + get_double(s[2:])
    else:
        return 0 + get_double(s[1:])

>>> print get_double(st)
4

OTHER TIPS

Not sure why you want to do this recursively. If you wish to avoid regex, you can still just scan the string from left to right. For example, using itertools.groupby

>>> from itertools import groupby
>>> s = 'aabbb'
>>> sum(sum(1 for i in g)//2 for k,g in groupby(s))
2
>>> s = 'yyourr ssstringg'
>>> sum(sum(1 for i in g)//2 for k,g in groupby(s))
4

sum(1 for i in g) is used to find the length of the group. If the groups are not very long you can use len(list(g)) instead

I would evaluate it by 2's.

for example "sskkkj" would be looked at as two sets of two char strings:

"ss", "kk", "kj" # from 0 index
"sk", "kk"  # offset by 1 

look at the two sets at the same time and add only one to the count if either has a pair.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top