How to check if a string is a substring of another even if not in order?

Question

Is there a way to check if a string contains another string but not necessairely in the correct order :

"hel my frend" in "hello my friend" = true
"hel my frend" in "my friend hello" = true
"hel my frend" in "h.e.l. .m.y. .f.r.e.n.d" = true
"hel my frend" in "my friend hello" = true

Answer 1

Change the substring to a regular expression with .* between each character, and then use re.search.

import re

def fuzzy_substring(needle, haystack):
    regex = ".*".join(re.escape(char) for char in needle)
    return re.search(regex, haystack)

re.escape is necessary in case any characters in the substring have special meaning in regular expressions.

Answer 2

You can use programmatically constructed regular expressions for it:

import re

def find_string(where, target):
    re_string = '.*'.join(target)
    REGEX = re.compile(re_string)
    return REGEX.findall(where)

print(find_string("hello my friend", "hel my frend"))
print(find_string("my friend hello", "hel my frend"))
print(find_string("h.e.l. .m.y. .f.r.e.n.d", "hel my frend"))

will print:

['hello my friend']
[]
['h.e.l. .m.y. .f.r.e.n.d']

So if the result of function contains 0 elements, it is equal to False, if 1 or more - True.

Answer 3

If I understand your question and the examples correctly, you could use colections.Counter to count the characters in both strings and see if there are any chars left after subtracting the second from the first.

from collections import Counter    
def isin(a, b):
    return not Counter(a) - Counter(b)

Positive examples:

isin("hel my frend", "hello my friend") # True
isin("hel my frend", "my friend hello") # True
isin("hel my frend", "h.e.l. .m.y. .f.r.e.n.d") # True

Negative Exampels:

isin("hel my frgend", "hello my friend") # False
isin("hel my frend", "my frind hello") # False
isin("hel my frend", "h.e.l. .m.. .f.r.e.n.d") # False

Answer 4

Python 3.10 added comparison operators to collections.Counter

from collections import Counter
a = Counter("hel my friend")
b = Counter("hello my friend")

is_a_in_b = a <= b  # True