如何在字符串中找到可以形成特定目标的每个子序列？

Question

例如，如果我得到一个字符串

s

=

"xTARGxxxxTARxETxxxxGET"

，我想遍历该字符串并存储对

1, 14

和

9, 21

，它们表示

s 中子序列的开始和结束索引

、

"TARGxxxxTARxET"

和

"TARxETxxxxGET"

，从中可以通过删除零个或多个字符来形成

"TARGET"

。

我知道每次到达

'T'

我都可以迭代，但我正在寻找更有效的解决方案。

Answer 1

你可以使用两个指针来解决这个问题，一个指针遍历字符串 s，另一个指针遍历字符串“TARGET”。这将允许您一次性检查输入字符串中的子序列。这是一个用于查找所需子序列的 Python 函数：

def find_target_subsequences(s):
    target = "TARGET"
    target_length = len(target)
    subsequences = []
    
    i = 0
    while i < len(s):
        start = None
        target_idx = 0
        
        while i < len(s) and target_idx < target_length:
            if s[i] == target[target_idx]:
                if start is None:
                    start = i
                target_idx += 1
            i += 1
        
        if target_idx == target_length:
            subsequences.append((start, i - 1))
    
    return subsequences

s = "xTARGxxxxTARxETxxxxGET"
print(find_target_subsequences(s))
# Output: [(3, 15), (9, 22)]

这个函数初始化了两个指针i和target_idx，并遍历字符串s找到“TARGET”的子序列。变量 start 存储有效子序列的起始索引。当整个“TARGET”字符串被匹配时（target_idx == target_length），该函数将子序列的开始和结束索引添加到子序列列表中。

Answer 2

您可以将目标词中每个字符的索引放入字典中（

defaultdict(list)

），然后从第一个字符开始使用

bisect_left

进行二分搜索并遍历每个字符直到目标词结束。

对起始字符的每个索引重复此操作。

最坏情况下的复杂性是你正在做的（起始字符索引数）*（（n-1）*binary_searches）。

代码未完全测试：

from collections import defaultdict
from bisect import bisect_left

def get_subs(s, t):
    d = defaultdict(list)
    for i, c in enumerate(s):
        if c in t:
            d[c].append(i)
    res = []
    done = False
    i = 0
    while i < len(d[t[0]]) and not done:
        v = d[t[0]][i]
        start_val = v
        j = 0
        while j + 1 < len(t):
            k = t[j + 1]
            if k == t[j]:
                v = v + 1
            pos = bisect_left(d[k], v)
            if pos == len(d[k]):
                done = True
                break
            end_val = d[k][pos]
            v = end_val
            j += 1
        if not done:
            res.append([start_val, end_val])
        i += 1
    return res

print(get_subs("xTARGxxxxTARxETxxxxGET", "TARGET"))
print(get_subs("xTARGxxxxTARxETxxTARGxxxETRGAxxxTEGExxxxxGET", "TARGET"))
print(get_subs("TATTTTRGETTTT", "TTT"))
print(get_subs("aaaaaaaaaaaaa", "a"))
print(get_subs("aaaaaaaaaaaaa", "aa"))
print(get_subs("aaaaaaaaaaaaa", "ab"))
print(get_subs("tratratataratarararart", "art"))

[[1, 14], [9, 21]]
[[1, 14], [9, 25], [14, 25], [17, 25]]
[[0, 3], [2, 4], [3, 5], [4, 9], [5, 10], [9, 11], [10, 12]]
[[0, 0], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6, 6], [7, 7], [8, 8], [9, 9], [10, 10], [11, 11], [12, 12]]
[[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [8, 9], [9, 10], [10, 11], [11, 12]]
[]
[[2, 6], [5, 12], [7, 12], [9, 12], [11, 21], [13, 21], [15, 21], [17, 21], [19, 21]]

您可以在 https://replit.com/@somdude/SomeDude?v=1

使用代码