string contains all chars ordered
Checking whether string a
contains all the characters in string b
in order can be done in O(n)
time and succinctly in python, by using an iterator.
1st = iter('hello')
2ar = 'el'
3print(all(c in st for c in ar))
This works because calling in
on an iterator will continue calling it.next()
until the item is met.
Therefore, iterating takes O(|a|)
and there will be O(max(|a|, |b|))
comparisons.
Time complexity: O(n)
See also: