check if letters of a string are in sequential order in another string

Question

If it were just checking whether letters in a test_string are also in a control_string,

I would not have had this problem.

I will simply use the code below.

if set(test_string.lower()) <= set(control_string.lower()):
    return True

But I also face a rather convoluted task of discerning whether the overlapping letters in the

control_string are in the same sequential order as those in test_string.

For example,

test_string = 'Dih'
control_string = 'Danish'
True

test_string = 'Tbl'
control_string = 'Bottle'
False

I thought of using the for iterator to compare the indices of the alphabets, but it is quite hard to think of the appropriate algorithm.

for i in test_string.lower():
    for j in control_string.lower():
        if i==j:
            index_factor = control_string.index(j)

My plan is to compare the primary index factor to the next factor, and if primary index factor turns out to be larger than the other, the function returns False.

I am stuck on how to compare those index_factors in a for loop.

How should I approach this problem?

Answer 1

You could just join the characters in your test string to a regular expression, allowing for any other characters .* in between, and then re.search that pattern in the control string.

>>> test, control = "Dih", "Danish"
>>> re.search('.*'.join(test), control) is not None
True
>>> test, control = "Tbl", "Bottle"
>>> re.search('.*'.join(test), control) is not None
False

---

Without using regular expressions, you can create an iter from the control string and use two nested loops,¹⁾breaking from the inner loop and else returning False until all the characters in test are found in control. It is important to create the iter, even though control is already iterable, so that the inner loop will continue where it last stopped.

def check(test, control):
    it = iter(control)
    for a in test:
        for b in it:
            if a == b:
                break
        else:
            return False
    return True

You could even do this in one (well, two) lines using all and any:

def check(test, control):
    it = iter(control)
    return all(any(a == b for b in it) for a in test)

Complexity for both approaches should be O(n), with n being the max number of characters.

¹⁾ This is conceptually similar to what @jpp does, but IMHO a bit clearer.

Answer 2

Here's one solution. The idea is to iterate through the control string first and yield a value if it matches the next test character. If the total number of matches equals the length of test, then your condition is satisfied.

def yield_in_order(x, y):
    iterstr = iter(x)
    current = next(iterstr)
    for i in y:
        if i == current:
            yield i
            current = next(iterstr)

def checker(test, control):
    x = test.lower()
    return sum(1 for _ in zip(x, yield_in_order(x, control.lower()))) == len(x)

test1, control1 = 'Tbl', 'Bottle'
test2, control2 = 'Dih', 'Danish'

print(checker(test1, control1))  # False
print(checker(test2, control2))  # True

@tobias_k's answer has cleaner version of this. If you want some additional information, e.g. how many letters align before there's a break found, you can trivially adjust the checker function to return sum(1 for _ in zip(x, yield_in_order(...))).