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

by 
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

More Related Contents:

  1. Find common substring between two strings
  2. Is the time-complexity of iterative string append actually O(n^2), or O(n)?
  3. Find longest repetitive sequence in a string
  4. Python string ‘in’ operator implementation algorithm and time complexity
  5. When splitting an empty string in Python, why does split() return an empty list while split(‘\n’) returns [”]?
  6. Python: find closest string (from a list) to another string
  7. String similarity metrics in Python [duplicate]
  8. How can I interleave or create unique permutations of two strings (without recursion)
  9. User input integer list [duplicate]
  10. String comparison in Python: is vs. == [duplicate]
  11. Simpler way to create dictionary of separate variables?
  12. What does preceding a string literal with “r” mean? [duplicate]
  13. Quicksort with Python
  14. Convert floating point number to a certain precision, and then copy to string
  15. Is there a generator version of `string.split()` in Python?
  16. Convert hex string to integer in Python
  17. Python string with space and without space at the end and immutability
  18. Time complexity of string concatenation in Python [duplicate]
  19. How to make a string’s content appears on screen as we type on keyboard? [duplicate]
  20. Perform a string operation for every element in a Python list
  21. Python reverse-stride slicing
  22. Gauss-Legendre Algorithm in python
  23. Print all items in a list with a delimiter
  24. Element-wise string concatenation in numpy
  25. How can I copy a Python string?
  26. Python: maximum recursion depth exceeded while calling a Python object
  27. Are strings pooled in Python?
  28. lower() vs. casefold() in string matching and converting to lowercase
  29. How can I convert string values from a dictionary, into int/float datatypes?
  30. Splitting a math expression string into tokens in Python

Leave a Comment