找到最小的 window 子串

Question

问题说要创建一个字符串，从字符串中取出 3 个不连续的字符并将其放入子字符串中并打印第一个字符和最后一个字符。

str="subliminal"
sub="bmn"

n = len(str)-3

for i in range(0, n):
    print(str1[i:i+4])
    if sub1 in str1:
        print(sub1[i])

这应该打印 3 到 8，因为 b 是第三个字母，n 是第八个字母。

我也不知道如何在不完全更改代码的情况下使代码适用于长度不超过 3 个字符的子字符串。

Answer 1

不确定这是否是您的意思。我假设子字符串已经有效，这意味着它包含非连续字母。然后我得到子字符串的第一个和最后一个字母，并使用列表理解创建字符串中所有字母的列表。然后我只是遍历字母并保存第一个和最后一个字母出现的位置。如有遗漏，hmu.

sub = "bmn"
str = "subliminal"

first_letter = sub[0]
last_letter = sub[-1]

start = None
end = None

letters = [let for let in str]

for i, letter in enumerate(letters):
    if letter == first_letter:
        start = i
    if letter == last_letter:
        end = i

if start and end:
    print(f"From %s to %s." % (start + 1, end + 1)) # Output: From 3 to 8.

Answer 2

您可以采用多种不同的方式，

这是一个灵魂，

import re 
def Func(String, SubString):
    patt = "".join([char + "[A-Za-z]" + "+" for char in sub[:-1]] + [sub[-1]])
    MatchedString = re.findall(patt, String)[0]
    FirstIndex = String.find(MatchedString) + 1
    LastIndex = FirstIndex + len(MatchedString) -1 
    return FirstIndex, LastIndex
string="subliminal"
sub="bmn"
FirstIndex, LastIndex = Func(string, sub)

这将 return 3, 8 并且您可以更改子字符串的长度，假设您只需要第一个匹配项

Answer 3

一些递归有益健康：

def minimum_window_substring(strn, sub, beg=0, fin=0, firstFound=False):

    if len(sub) == 0 or len(strn) == 0:
        return f'From {beg + 1} to {fin}'
    elif strn[0] == sub[0]:

        return minimum_window_substring(strn[1:], sub[1:], beg, fin + 1, True)

    if not firstFound:
        beg += 1
    return minimum_window_substring(strn[1:], sub, beg, fin + 1, firstFound)

解释：

基本情况是，如果我们得到原始字符串或子字符串的长度为 0，我们就会停止并打印原始字符串中子字符串的开头和结尾。

如果当前字符串的第一个字母相等，那么我们开始计数器（我们用标志“firstFound”固定开头的“beg”）然后递增直到我们完成（sub 是一个空字符串/原始字符串是空）

一些思考/更多解释：

例如，如果您要求子字符串的 第一次 出现，例如，如果原始字符串是 "sububu subulum" 和 sub 等于 "sbl" 然后当我们点击我们的第一个 "s" - 这意味着它将 100% 从那里开始，因为如果另一个 "sbl" 在里面原始字符串 - 那么它必须包含剩余的字母，因此我们可以说它们属于第一个 s。（一个可怕的解释，我很抱歉）我想说的是，如果我们有 2 次出现子字符串 - 那么我们会选择第一个，无论如何。

注意：这个函数并不关心sub字符串是否包含连续的字母，也不检查字符是否在字符串本身中，因为你说我们必须从原始字符串中得到字符。它的积极之处在于，该函数可以给出多于（或少于）3 个字符的长子字符串

当我说“原始字符串”时，我的意思是 subliminal（或其他输入）

找到最小的 window 子串

finding the minimum window substring

python

substring

python-3.x

解释：

一些思考/更多解释：