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

Question

如果只是检查test_string中的字母是否也在control_string中，那么我就没有问题了。我会使用如下代码。

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

但是我也面临一个相当复杂的任务，需要辨别控制字符串中重叠的字母是否与测试字符串中的顺序相同。

例如，

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。

我应该如何解决这个问题？

- V Anon

Answer 1

你可以将你的测试字符串中的字符join起来，然后使用正则表达式，在其中允许任何其他字符.*，然后在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

---

不使用正则表达式，您可以从control字符串创建一个iter并使用两个嵌套循环，在内部循环中使用break并返回False，直到在control中找到test中的所有字符。重要的是创建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所做的，但我认为更清晰一些。

- tobias_k

Answer 2

这是一种解决方案。思路是首先遍历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

"

@tobias_k 的答案 是更干净的版本。如果您想要一些额外的信息，例如在找到换行符之前有多少个字符对齐，则可以轻松调整 checker 函数返回 sum（1 for _ in zip（x，yield_in_order（...）））。

"

- jpp

---

这实际上接近我的第二个解决方案(我没有看到)，但看起来过于复杂。为什么要yield i并将其与j进行比较？你已经知道它们是相等的。难道你不能只检查所产生的元素数量吗？ - tobias_k

@tobias_k，说得好。我确实尝试过 sum(1 for _ in yield_in_order(x, control.lower())) == len(x)，但是我收到了 DeprecationWarning: generator 'yield_in_order' raised StopIteration 的警告[我不理解]，即使结果是正确的。 - jpp

我猜当 iterstr 耗尽并尝试匹配更多字符时，就会出现这种情况。使用 x 进行压缩限制了从生成器中请求的项数。所以将它们进行 zip 似乎是有道理的，但是 == 仍然是多余的。 - tobias_k

@tobias_k，是的，花了一点时间但是我弄明白了...可以用sum(1 for ...)来实现。不过你的解决方案更清晰。 - jpp

Answer 3

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

- Frane

Answer 4

递归是解决这类问题的最佳方法。 以下是一个检查顺序排序的示例。

def sequentialOrder(test_string, control_string, len1, len2): 

    if len1 == 0:     # base case 1
        return True

    if len2 == 0:     # base case 2
        return False

    if test_string[len1 - 1] == control_string[len2 - 1]: 
        return sequentialOrder(test_string, control_string, len1 - 1, len2 - 1)  # Recursion 

    return sequentialOrder(test_string, control_string, len1, len2-1)

test_string = 'Dih'
control_string = 'Danish'

print(isSubSequence(test_string, control_string, len(test_string), len(control_string)))

输出：

True

并且返回False

test_string = 'Tbl'
control_string = 'Bottle'

这是一种迭代方法，可以完成相同的事情，

def sequentialOrder(test_string,control_string,len1,len2): 

    i = 0
    j = 0

    while j < len1 and i < len2: 
        if test_string[j] == control_string[i]:     
            j = j + 1    
        i = i + 1

    return j==len1 

test_string = 'Dih'
control_string = 'Danish'

print(sequentialOrder(test_string,control_string,len(test_string) ,len(control_string)))

- Vineeth Sai

---

你介意详细说明len1和len2的功能吗？我刚开始学习Python，对递归不熟悉。 - V Anon

递归不仅适用于Python，它们是一种方法。我一会儿也会用迭代的方法写出来。 - Vineeth Sai

@VAnon 我已经更新了我的答案。 - Vineeth Sai

Answer 5

一个简单的方法是利用sorted中的key参数，它作为排序比较的关键字：

def seq_order(l1, l2):
    intersection = ''.join(sorted(set(l1) & set(l2), key = l2.index))
    return True if intersection == l1 else False

因此，这是计算两个集合的交集并根据较长的字符串进行排序。完成后，您只需要将结果与较短的字符串进行比较，以查看它们是否相同。

该函数相应地返回True或False。使用您的示例：

seq_order('Dih', 'Danish')
#True

seq_order('Tbl', 'Bottle')
#False

seq_order('alp','apple')
#False

- yatu

Answer 6

使用生成器的优雅解决方案：

def foo(test_string, control_string):
    if all(c in control_string for c in test_string):
        gen = (char for char in control_string if char in test_string)
        if all(x == test_string[i] for i, x in enumerate(gen)):
            return True
    return False

print(foo('Dzn','Dahis')) # False
print(foo('Dsi','Dahis')) # False
print(foo('Dis','Dahis')) # True

首先检查test_string中的所有字母是否都包含在control_string中。然后检查顺序是否与test_string的顺序相似。

- b-fg

---

为什么该函数返回 ('Ce', 'Arsenic') 为 True？按理说，因为顺序是反过来的（ec），它不应该返回 false 吗？ - V Anon

你测试过这个吗？它实际上返回了False。 - b-fg

确实它返回了False！我想之前的执行还在运行。 - V Anon

这个解决方案的一个问题是重复的 if _ in test_string.. 或许可以使用 set 使其变为 O(1)？ - jpp

你是指 set 是什么意思？ - b-fg