检查字符串的字母是否在另一个字符串中按顺序排列

Question

如果它只是检查test_string中的字母是否也在control_string中,

我不会遇到这个问题.

我将简单地使用下面的代码.

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

但我也面临着一个相当复杂的任务,即辨别是否重叠的字母

control_string与test_string中的顺序相同.

例如,

test_string = 'Dih'
control_string = 'Danish'
True

test_string = 'Tbl'
control_string = 'Bottle'
False

我想过使用for迭代器来比较字母表的索引,但是很难想到合适的算法.

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

我的计划是将主要指标因子与下一个因子进行比较,如果主要指数因子大于另一个,则该函数返回False.

我被困在如何比较for循环中的那些index_factors.

我该如何处理这个问题？

Answer 1

您可以join将test字符串中的字符添加到正则表达式中,允许.*其间的任何其他字符,然后re.search是control字符串中的该模式.

>>> 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

如果不使用正则表达式,你可以创建一个iter从control字符串,并使用两个嵌套循环,¹⁾ break从内环路荷兰国际集团和else返回False,直到所有的人物test中被发现control.iter尽管control已经可迭代,但创建尽可能重要,以便内循环将在上次停止的位置继续.

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

您甚至可以使用all和在一个(两个)行中执行此操作any:

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

两种方法的复杂度应为O(n),其中n为最大字符数.

¹⁾这在概念上与@jpp的相似,但恕我直言更清楚.

Answer 2

您可以find(letter, last_index)在处理字母后查找所需字母的出现情况。

def same_order_in(test, control):
    index = 0
    control = control.lower()
    for i in test.lower():
        index = control.find(i, index)
        if index == -1:
            return False
        # index += 1 # uncomment to check multiple occurrences of same letter in test string  
    return True

如果测试字符串有重复的字母，例如：

test_string = 'Diih'
control_string = 'Danish'

带注释行same_order_in(test_string, control_string) == True

并带有未注释的行same_order_in(test_string, control_string) == False