How to test if one string is a subsequence of another?
algorithm, python, string
Solution
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)
Problem
How to test if one string is a subsequence of another? 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