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

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

您可以使用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

Answer 2

您可以仅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字符串创建一个并使用两个嵌套循环，1) 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

您甚至可以使用alland在一行（好吧，两行）中执行此操作any：

def check(test, control):

    it = iter(control)

    return all(any(a == b for b in it) for a in test)

这两种方法的复杂度应该是 O(n)，n 是最大字符数。

Answer 3

这是一种解决方案。我们的想法是通过遍历control字符串第一，如果接下来的比赛产生一个值test字符。如果匹配的总数等于 的长度test，则满足您的条件。

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

如果您需要一些附加信息，例如在找到中断之前对齐了多少个字母，您可以简单地将checker函数调整为 return sum(1 for _ in zip(x, yield_in_order(...)))。