How to test if one string is a subsequence of another?

Question

This is a weaker condition than being a substring. For example 'iran' is not a substring of 'ireland', but it is a subsequence IRelANd. The difference is a subsequence doesn't have to be contiguous.

More examples:

'indonesia' contains 'india'. INDonesIA
'romania' contains 'oman'. rOMANia
'malawi' contains 'mali'. MALawI

Movitation: My friends like word games. Yesterday we played 'countries within countries'. I am curious if there are any pairs we missed.

Edit: If you aren't familiar with the mathematical definition of subsequence

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements

falsetru · Accepted Answer · 2016-07-05 11:30:41Z

55

def is_subseq(x, y):
    it = iter(y)
    return all(any(c == ch for c in it) for ch in x)

assert is_subseq('india', 'indonesia')
assert is_subseq('oman', 'romania')
assert is_subseq('mali', 'malawi')
assert not is_subseq('mali', 'banana')
assert not is_subseq('ais', 'indonesia')
assert not is_subseq('ca', 'abc')

Also works for any iterables:

assert is_subseq(['i', 'n', 'd', 'i', 'a'],
                 ['i', 'n', 'd', 'o', 'n', 'e', 's', 'i', 'a'])

UPDATE

Stefan Pochmann suggested this.

def is_subseq(x, y):
    it = iter(y)
    return all(c in it for c in x)

Both versions uses iterators; Iterator yields items that was not yielded in previous iteration.

For example:

>>> it = iter([1,2,3,4])
>>> for x in it:
...     print(x)
...     break
...
1
>>> for x in it:  # `1` is yielded in previous iteration. It's not yielded here.
...     print(x)
...
2
3
4

edited Jul 5, 2016 at 11:30

answered Jun 3, 2014 at 14:24

falsetru

371k69 gold badges769 silver badges659 bronze badges

Sign up to request clarification or add additional context in comments.

15 Comments

falsetru Over a year ago

@user189, According to the quote in the question, order is important; ca is not a subsequence of abc.

user189 Over a year ago

Ok, misunderstood the use of an iterator here, seems quite clever.

Stefan Pochmann Over a year ago

What do you think of all(c in it for c in x)? Does something speak against it?

falsetru Over a year ago

@user2361174, it in the answer is an iterator. Item that is iterated is not iterated again. (consumed)

RoyM Over a year ago

Just brilliant!! took a while to grok this, but I love it

|

wim · Accepted Answer · 2021-09-14 19:45:18Z

11

Just keep on looking for the next character of your potential subsequence, starting behind the last found one. As soon as one of the characters can't be found in the remainder of the string, it's no subsequence. If all characters can be found this way, it is:

def is_subsequence(needle, haystack):
    current_pos = 0
    for c in needle:
        current_pos = haystack.find(c, current_pos) + 1
        if current_pos == 0:
            return False
    return True

An advantage over the top answer is that not every character needs to be iterated in Python here, since haystack.find(c, current_pos) is looping in C code. So this approach can perform significantly better in the case that the needle is small and the haystack is large:

>>> needle = "needle"
>>> haystack = "haystack" * 1000
>>> %timeit is_subseq(needle, haystack)
296 µs ± 2.09 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> %timeit is_subsequence(needle, haystack)
334 ns ± 1.51 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

edited Sep 14, 2021 at 19:45

wim

368k114 gold badges681 silver badges818 bronze badges

answered Jun 3, 2014 at 14:18

KillianDS

17.2k4 gold badges64 silver badges73 bronze badges

2 Comments

r.e.s. Over a year ago

@wim Can this be made to work with lists?

wim Over a year ago

@r.e.s. See stackoverflow.com/a/52709319/674039 - I don't believe the string fast path that this answer exploits will be possible with lists.

Colonel Panic · Accepted Answer · 2014-06-03 14:14:51Z

0

I did

def is_subsequence(x, y):
    """Test whether x is a subsequence of y"""
    x = list(x)
    for letter in y:
        if x and x[0] == letter:
            x.pop(0)

    return not x

answered Jun 3, 2014 at 14:14

Colonel Panic

138k98 gold badges420 silver badges483 bronze badges

1 Comment

Aran-Fey Over a year ago

Deleting from the left of a list is awfully inefficient, especially if you do it in a loop. And it's completely unnecessary here; you could/should just use an iterator instead.

Josip Grggurica · Accepted Answer · 2014-06-03 14:34:44Z

-3

def subsequence(seq, subseq):
    seq = seq.lower()
    subseq = subseq.lower()
    for char in subseq:
        try:      
            seq = seq[seq.index(char)+1:]            
        except:
            return False
    return True

answered Jun 3, 2014 at 14:34

Josip Grggurica

4214 silver badges12 bronze badges

1 Comment

Aran-Fey Over a year ago

Repeatedly slicing the input sequence is needlessly inefficient; using an iterator (or index) would be much better.

Collectives™ on Stack Overflow

How to test if one string is a subsequence of another?

4 Answers 4

15 Comments

2 Comments

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

15 Comments

2 Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related