2
\$\begingroup\$

Algorithm: Determine if an array of arrays of characters can be concatenated in order, into a substring of haystack.

Example:

[['a','A','@'], ['b','B','8'], ['c','(','[']]

This list can be combined by selecting from each of the subarrays in order, such as:

abc, ab(, ab[, Abc, Ab( etc.

Are any of these combinations substrings of the search string?

"123 easy as Ab(" # True
"123 easy as Abb" # False
"123 easy as @b(" # True
"123 easy as Abc" # False

Python 3

combos = [['a','A','@'], ['b','B','8'], ['c','(','[']]
search = "123 easy as Ab(" # True

def find_mutated_string(offset, combos, search):
    for i, char in enumerate(search):
        for mutant in combos[offset]:
            if mutant == char:
                if len(combos) == (offset+1):
                    # Last letter combo found
                    return True
                else:
                    return find_mutated_string(offset+1, combos, search[i+1:])
    # Didn't find mutant char in search string
    return False

print(find_mutated_string(0, combos, search))
\$\endgroup\$
3
\$\begingroup\$

bug

You don't reset the offset when there is a mismatch, so "123 easy as b(" also returns True. Just add:

    else:
        offset = 0

optional parameter offset

The caller of the function should not care about the offset if he wants to check whether a combination is part of the string. I would change the method signature to def find_mutated_string2(combos, search, offset=0). Then your user doesn't need to worry about this

in

Python has the in statement.

Your code says

    for mutant in combos[offset]:
        if mutant == char:

but actually mean: if char in combos[offset]

Since in in a list traverses the list to look for a match, while set uses a lookup, defining the combos as sets helps here

combos = [{"@", "A", "a"}, {"8", "B", "b"}, {"(", "[", "c"}]


def find_mutated_string2(combos, search, offset=0):
    for i, char in enumerate(search):
        if char in combos[offset]:
            if len(combos) == (offset + 1):
                return True
            else:
                return find_mutated_string2(combos, search[i+1:], offset+1)
        else:
            offset = 0
    return False

match substring

You could write a helper function that takes a substring and checks whether this matches the combo's

def matches_combos(substring, combos):
    return len(substring) == len(combos) and all(
        char in combo for char, combo in zip(substring, combos)
    )

This can be easily tested:

test_cases = {
    "abc": True,
    "Ab[": True,
    "abd": False,
    "ab": False,
    "abcd": False,
}
for substring, answer in test_cases.items():
    result = matches_combos(substring, combos)
    assert result == answer

recursion

If your string is long, you will run into the recursion limit.

for i in range(10000):
    try:
        _ = find_mutated_string2(combos, "a"*i)
    except RecursionError:
        print(f"fails for string length: {i}")
        break
fails for string length: 5921

for a recursionlimit of 3000

You can easily rewrite this proble iteratively

def find_mutated_string3(combos, search):
    if len(search) < len(combos):
        return False
    for i in range(len(search) - 2):
        substring = search[i : i + len(combos)]
        if matches_combos(substring, combos):
            return True

or using any

def find_mutated_string4(combos, search):
    if len(search) < len(combos):
        return False
    return any(
        matches_combos(search[i : i + len(combos)], combos)
        for i in range(len(search) - 2)
    )
\$\endgroup\$
  • \$\begingroup\$ Thanks a bunch! How likely am I to hit the recursion limit? I guess the search string must be at least 998 characters or so for this to happen? \$\endgroup\$ – deed02392 May 8 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.