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

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))


# 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.

    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,
}
result = matches_combos(substring, combos)


# 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)
)

• 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? May 8, 2019 at 16:01