A Concise Python Function to Check Subsequence using Iterator

Given a list/array/string in Python, find out if it is the subsequence of another. A subsequence X of Y is the sequence that removes non or more elements of Y so that X == Y. For example, “abc” is a subsequence of “atbtc”.

To implement this subsequence check, it usually involves two pointers pointing to X and Y and move them towards the end. But in Python, we can do this quick and efficient using the iterator, and the all, any function:

1
2
3

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

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

For example:

1
2
3
4

>>> isSubsequence("abc", "def")
False
>>> isSubsequence("abc", "adebcf")
True

>>> isSubsequence("abc", "def")
False
>>> isSubsequence("abc", "adebcf")
True

First, we need to get the iterator of y, then the iterator will keep moving to the right (won’t reset) if possible – via any function. Then finally, we have to make sure for all characters in x, we can find a match in y.

Of course, we can use two pointer to implement this in a classic way Teaching Kids Programming – Is Subsequence Algorithm via Two Pointer:

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        ls, lt = len(s), len(t)
        if ls > lt:
            return False
        i = j = 0
        while i < ls and j < lt:
            if s[i] == t[j]:
                i += 1
                j += 1
            else:
                j += 1
        return i == ls

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        ls, lt = len(s), len(t)
        if ls > lt:
            return False
        i = j = 0
        while i < ls and j < lt:
            if s[i] == t[j]:
                i += 1
                j += 1
            else:
                j += 1
        return i == ls

String Subsequence Algorithms:

• Teaching Kids Programming – Is Subsequence Algorithm via Recursion (Greedy)
• Teaching Kids Programming – Is Subsequence Algorithm via Two Pointer
• The Subsequence Algorithm for Two Strings – How to Check if a String is Subsequence of Another?
• GoLang Function of Checking Is Subsequence
• Algorithms to Check if a String is a Subsequence String of Another String
• in Python, you can do this in Pythonic way: Python Function to Check Subsequence

–EOF (The Ultimate Computing & Technology Blog) —