Finding subsequence (nonconsecutive)

Question

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

score 18 · Accepted Answer · answered Apr 29 '15 at 21:22

18

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

answered Apr 29 '15 at 21:22

Ishamael

12,123
4
31
50

2

I like that this has linear time complexity – user4847061 Apr 29 '15 at 21:33
`exists("haystack", "")` returns True. Add `if len(b) == 0: return False` to the answer – pouya Oct 02 '21 at 17:16

wim · Answer 2 · 2018-10-10T16:06:38.120

17

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.

edited Oct 10 '18 at 16:06

answered Oct 08 '18 at 20:01

wim

302,178
90
548
690

2

For anyone else who tries to inline `it`, that is, tries to do it one line like: `all(x in iter(haystack) for x in needle)`, it doesn't work because `iter(haystack)` is re-instantiated each time. – Garrett May 06 '20 at 01:15
This implementation is **in average 1000 times faster** than @Ishamael implementation – pouya Oct 02 '21 at 18:55

score 5 · Answer 3 · answered Apr 29 '15 at 21:27

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

score -1 · Answer 4 · answered Sep 23 '20 at 03:16

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

Finding subsequence (nonconsecutive)

4 Answers4

Linked

Related