Check if a string is interleaving of two other given strings using recursion-CodePudding

I want to check if s3 is an organized combination of s1 and s2. so I wrote this:

def organized_comp(s1,s2,s3):
    l1, l2, l3 = len(s1), len(s2),len(s3)
    if (l1 == 0 and l2 == 0 and l3 ==0):
        return True
    if (l1 == 0 and s2 == s3) or (l2 == 0 and s1 == s3):
        return True
    if (l3 != (l1  l2)) or (l3 == 0 and (l1 > 0 or l2 > 0)):
        return False    
    if s1 and s1[0] == s3[0]:
        return True and organized_comp(s1[1:], s2, s3[1:])
    if s2 and s2[0] == s3[0]:
        return True and organized_comp(s1, s2[1:], s3[1:])

when I send : s1 = "ABZ" , s2 = "ABAXZ", s3 = "ABAXABZZ" it returns False and it needs to return True. I think I know the problem - because s1[0] = s2[0] and it always start with s1 (If I send s2 = "ABZ" , s1 = "ABAXZ" it works).

how I can correct it?

CodePudding user response：

Your analysis of the issue is correct: if s1[0] == s2[0], then you don't know which character should be used. So, you should try both possibilities, and return True if at least one of them works.

This can be accomplished with logical operator or.

Also note that your "if forest" was missing a case where it should return False: when l1 l2 == l3 but s3[0] not in (s1[0], s2[0]). In python, as opposed to almost every other programming language, if a return is missing in a function, python doesn't crash and the function silently returns None as if there had been an explicit return None. So, the way you wrote it, organized_comp('a', 'b', 'c') would return None instead of False.

Some of your conditions were a bit redundant, for instance the two following conditions would be equivalent:

(l3 != (l1  l2)) or (l3 == 0 and (l1 > 0 or l2 > 0))
(l3 != (l1  l2)) # if the second part was True, then the first part would be True anyway

Here is a proposed fix:

def organized_comp(s1,s2,s3):
    l1, l2, l3 = len(s1), len(s2),len(s3)
    return (l3 == l1   l2) and (
        (l3 == 0) or
        (l1 > 0 and s3[0] == s1[0] and organized_comp(s1[1:], s2, s3[1:])) or
        (l2 > 0 and s3[0] == s2[0] and organized_comp(s1, s2[1:], s3[1:]))
    )

CodePudding user response：

Found in comments, that OP needs a solution without `replace`

A solution without replace:

s1 = "ABZ"
s2 = "ABAXZ"
base = "ABAXABZZ"

def is_combination_of(base: str, p1: str, p2: str):
    if len(base) > 0:
        try:
            p1i = p1.index(base[0])
            return is_combination_of(base[1:], p1[:p1i]   p1[p1i 1:], p2)
        except ValueError:
            pass
        try:
            p2i = p2.index(base[0])
            return is_combination_of(base[1:], p1, p2[:p2i]   p2[p2i 1:])
        except ValueError:
            pass
    if base == p1 == p2 == '':
        return True
    return False

print(is_combination_of(base, s1, s2))

Your mistake is the assumption that for each first character in s3 you can find that character as the first character of s1 or s2. This approach fails for this simplified case:

s1 = 'CA'
s2 = 'CB'
s3 = 'ABCC'

As you can see, you need to look at all characters of s1 and s2 to find out if s3[0] is in them.

The recursive approach is needless for this exact case, but if you want, it could be done this way:

s1 = "ABZ"
s2 = "ABAXZ"
base = "ABAXABZZ"

def is_combination_of(base: str, p1: str, p2: str):
    if len(base) > 0:
        if base[0] in p1:
            return is_combination_of(base[1:], p1.replace(base[0], '', 1), p2)
        if base[0] in p2:
            return is_combination_of(base[1:], p1, p2.replace(base[0], '', 1))
    if base == p1 == p2 == '':
        return True
    return False

print(is_combination_of(base, s1, s2))

But it's a very inefficient way to do it. I mean, with recursion.

Found in comments, that OP needs a solution without replace

Found in comments, that OP needs a solution without `replace`