string recursion problems

Question

I am relatively new to python and especially recursion. I have been trying to solve this problem for a while now but it's bested me so far

I have to create a function that takes in 2 strings and uses recursion to see if elements from the first string are in the second string if so it returns true if not than it returns false say "Carpool" and "prlo" or "elephant" and "xph" in the first case the recursive argument would return True and in the second case it would return False.

This is what I've been trying to do. I set a count so that if the elements match I can increase it and at the end if it's equal to len(str2) then I print 2. The major problem is iterating through the 2 strings separately, any idea on how I should approach this?

def compare(str1,str2):

count = 0
if str1 == str2:
    return "True"           
elif str1[0] == str2[0]:
    count = count + 1
    return letCheck (str1[1:],str2)
elif str1[0] != str2[0]:
    return letCheck (str1[1:],str2)

are you sure you have the outline of the function correct? Are you meant to check if each char of str1 is in str2? — Padraic Cunningham
– Padraic Cunningham, Commented Jul 28, 2014 at 0:11
So if i get this right you want to return true if str1 shares characters with str2 and count them as well? — gkrls
– gkrls, Commented Jul 28, 2014 at 0:12
to make it clear yes, I need to see if the char in str1 match the char in str2 order doesn't matter what order they appear in. I don't have to count just return true if char from str2 appear in str1 as shown in the 2 examples — H.H.
– H.H., Commented Jul 28, 2014 at 0:14
why did you not just use in, is there some requirement that prevents this? — Padraic Cunningham
– Padraic Cunningham, Commented Jul 28, 2014 at 0:30

John1024 · Accepted Answer · 2014-07-28 00:28:03Z

2

def compare(s1, s2):
    if not s2:
        return True
    elif s2[0] in s1:
        return compare(s1, s2[1:])
    else:
        return False

On your examples:

>>> compare( "Carpool" , "prlo")
True
>>> compare("elephant", "xph")
False

How it works

The function processes each character in string 2, s2, one at a time. There are three cases:

If there are no characters left to process in s2, that means that all the tests have passed and we return True.
If there are still characters left in s2, then we test s2[0]. If it passes, we then use recursion to test the rest of the string.
If s2[0] is not in s1, then we have a fail and we return False.

edited Jul 28, 2014 at 0:28

answered Jul 28, 2014 at 0:21

John1024

115k15 gold badges152 silver badges183 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

name not found · Accepted Answer · 2014-07-28 00:24:15Z

0

You don't need a counter. You can just check if the first letter of the first String (str1) is in the second string (str2). If so, then check if this was the last character of the first string. If it wasn't the last character, pass the rest of the string to the function again (recursion). And if one character of the first string is not in the second one, you return False.

def compare(str1, str2):
    if str1[0] in str2:
        if len(str1) == 1:
            return True;
        return compare(str[1:0], str2);
    else:
        return False;

print compare('ak', 'abcd');  # False
print compare('cd', 'abcd');  # True
print compare('efgh', 'efg'); # False

answered Jul 28, 2014 at 0:24

name not found

6224 silver badges14 bronze badges

Comments

Padraic Cunningham · Accepted Answer · 2014-07-28 00:58:46Z

This will return False if str2 is passed in as an empty string:

def letCheck(str1, str2, count = 0):
    if str1 == str2: # both strings are equal,we don't have to  go any further
        return True
    elif str2 == "" and count == 0: # if str2 is empty and count is 0 we got passed an empty str2
        return False
    elif len(str2) == count: # if count and len are equal, all str2 letters are in str1
        return True
    elif str2[0] in str1:
        count += 1 # increase count and move to the next letter in str2[1:]
        return letCheck(str1, str2[1:],count)
    return False # if we get here we have found a letter that is not in str1

When using a variable like count, you need to use it as a parameter to keep the value between each recursive call or else it will get reset to 0 each call.

Collectives™ on Stack Overflow

string recursion problems

3 Answers 3

How it works

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

How it works

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related