Finding subsequence (nonconsecutive)

If I have string needle and I want to check if it exists contiguously as a substring in haystack, I can use:

if needle in haystack:
    ...

What can I use in the case of a non-continuous subsequence? Example:

>>> haystack = "abcde12345"
>>> needle1 = "ace13"
>>> needle2 = "123abc"
>>> is_subsequence(needle1, haystack)
True
>>> is_subsequence(needle2, haystack)  # order is important!
False

Answers:

Thank you for visiting the Q&A section on Magenaut. Please note that all the answers may not help you solve the issue immediately. So please treat them as advisements. If you found the post helpful (or not), leave a comment & I’ll get back to you as soon as possible.

Method 1

I don’t know if there’s builtin function, but it is rather simple to do manually

def exists(a, b):
    """checks if b exists in a as a subsequence"""
    pos = 0
    for ch in a:
        if pos < len(b) and ch == b[pos]:
            pos += 1
    return pos == len(b)

>>> exists("moo", "mo")
True
>>> exists("moo", "oo")
True
>>> exists("moo", "ooo")
False
>>> exists("haystack", "hack")
True
>>> exists("haystack", "hach")
False
>>>

Method 2

Using an iterator trick:

it = iter(haystack)
all(x in it for x in needle)

This is only a concise version of the same idea presented in another answer.

Method 3

Another possibility: You can create iterators for both, needle and haystack, and then pop elements from the haystack-iterator until either all the characters in the needle are found, or the iterator is exhausted.

def is_in(needle, haystack):
    try:
        iterator = iter(haystack)
        for char in needle:
            while next(iterator) != char:
                pass
        return True
    except StopIteration:
        return False

Method 4

We can try simple for loop and break method and pass on substring once the match is found

def substr(lstr,sstr):
lenl = len(lstr)
for i in sstr:
    for j in range(lenl):
        if i not in lstr:
            return False
        elif i == lstr[j]:
            lstr = lstr[j+1:]
            break
        else:
            pass
return True

All methods was sourced from stackoverflow.com or stackexchange.com, is licensed under cc by-sa 2.5, cc by-sa 3.0 and cc by-sa 4.0