没有 Y 分而治之的最长子串

Question

在我继续这个问题之前，我应该注意我知道有更简单的方法来解决这个问题而不使用分而治之；然而，在这种限制下解决这个问题的重点是我实际上想学习如何用分而治之的方式解决问题。我擅长识别正确的解决方案，但实施我自己的 D&C 策略不是我目前的技能。

问题是这样的：给定一个字符串，找到不包含字母'y'的最长子串。例如， longestNoY("abydefyhi") 应该 return "def".

我解决这个问题的第一个方法是确定基本情况。如果我们有一个长度为 2 的字符串，我们希望 return non-y 组件（或者如果两个字符都是 'y' 则为空字符串）。如果我们有一个长度为 1 的字符串，如果它不是 'y'，我们将 return 它。

所以第一部分应该是这样的：

def longestNoY(string, start, end):
     #Conquer
     if start == end:
          if string == 'y': return ''
          return string
     if start + 1 == end:
          if string == "yy": return ''
          if string[0] == 'y': return string[1]
          return string[0]
     ....

接下来，我知道我需要为 parent 字符串的每一半递归调用该函数。我也知道我希望函数 return 两个 children 中较长的一个，除非两个 children 的长度之和等于 [=41] 的长度=]，那么函数应该 return 和 parent，因为 children 中没有 'y'。

    #Divide and Partial Implementation of Rejoin
    ....
    middle = (start + end) // 2
    leftString = longestNoY(string, start, middle)
    rightString = longestNoY(string, middle, end)
    if len(leftString) + len(rightString) == len(string): return string
    ....

我现在遇到问题的部分最好用一个例子来解释：

0 1 2     3 4   5 6   7 8 
a b   y   d e | f y   h i
a b   y | d e | f y | h i
a b | y | d e | f y | h i

左侧最长的子串是 "ab" 或 "de"，但我们知道 "de" 与 'f' 相邻，这将使 "def" 最长的。我不知道如何继续解决这个问题。请不要给我一个程序来解决这个问题。

Answer 1

有可能。但是你每次都需要 return 四个值：从 "slice" 的左端开始的最长子序列（这可以是零），最长的子序列 "in the middle"，在 "slice" 右端结束的最长子序列（也可以为零），如果字符串只是一个非 Y 字符序列（布尔值）。第四个元素实际上可以通过检查前三个元素中的一个元素是否等于长度来导出，但这可能更容易实现。

为什么这很重要？因为一系列非 y 可以通过 "through" 一个鸿沟。例如：

abcde<b>Y</b>fghi   jkl<b>Y</b>mnopqr

如果我们在中间拆分它（或任何其他不是 "constant" 和 "rest" 的方式）。

所以这里递归我们有几种情况：

空串returns (0, 0, 0, True),
除Y以外的非空字符串，我们return (1, 1, 1, True);
对于单例字符串 Y 我们 return (0, 0, 0, False);
将字符串一分为二的递归情况，然后在结果上应用 "merge" 逻辑。

"merge logic" 相当复杂，尤其是因为两个 "subslices" 都可能只包含非 Y 字符串。切片后我们得到两个三元组 (a0, a1, a2, a3) 和 (b0, b1, b2, b3)，我们产生一个三元组 (c0, c1, c2, c3).

如果a3 = True和b3 = True，那么当然意味着当前切片也不包含Y。所以我们可以得出：

c3 = a3 and b3

给定 a3 成立，然后它认为 c0 = a0 + b0 从那时起 a0 没有 Y，因此左边的 "sequence" 与整个长度相同subsequence plus 右边部分的左边子序列。如果 a3 不成立，c0 就是 a0.

鉴于b3成立，则c2 = a2 + b2成立，同上，如果不成立，则a2 = b2.

现在中间的元素是三个元素中的最大值:

左切片中间的元素a1;
右切片中间的元素b1;和
a2和b0的总和，因为可以重叠，所以这是两者的总和。

我们因此return树的最大值。

所以在 Python 中，这看起来像：

def longestNoY(string, start, end):
    if start == end:
        return (0, 0, 0, True)
    elif start+1 == end:
        if string[start] == 'y':
            return (0, 0, 0, False)
        else:
            return (1, 1, 1, True)
    else:
        mid = (start + end)//2
        a0, a1, a2, a3 = longestNoY(string, start, mid)
        b0, b1, b2, b3 = longestNoY(string, mid, end)
        c3 = a3 and b3
        c0 = a0 + a3 * b0
        c2 = b2 + b3 * a2
        c1 = max(a1, b1, a2 + b0)
        return (c0, c1, c2, c3)

最终结果是元组中前三项中的最大值。

对于给定的样本字符串，我们因此得到：

             (1, 1, 1, True) a
             (1, 1, 1, True) b
         (2, 2, 2, True) ab
             (0, 0, 0, False) y
             (1, 1, 1, True) d
         (0, 1, 1, False) yd
     (2, 2, 1, False) abyd
             (1, 1, 1, True) e
             (1, 1, 1, True) f
         (2, 2, 2, True) ef
             (0, 0, 0, False) y
                 (1, 1, 1, True) h
                 (1, 1, 1, True) i
             (2, 2, 2, True) hi
         (0, 2, 2, False) yhi
     (2, 2, 2, False) efyhi
 (2, 3, 2, False) abydefyhi
(2, 3, 2, False)

但话虽这么说，但在我看来，它看起来是一个不必要的复杂过程来构造一些东西，就时间复杂度而言，它与遍历相同，但通常更昂贵（函数调用、构造新对象等）。 ).特别是因为线性遍历只是：

def longestNoY(string):
    mx = 0
    cur = 0
    for c in string:
        if c == 'y':
            mx = max(mx, cur)
            cur = 0
        else:
            cur += 1
    return mx

然而，这里的一个优点是上述算法可用于并行化。例如，如果字符串很大，则可以使用上面的方法，以便每个内核都可以计算它。然而，在这种情况下，在 "core" 级别上使用迭代级别可能是有益的，并且仅使用以上内容来 "distribute" 工作和 "collect" 结果。

Answer 2

只要遍历字符串就可以很容易地解决这个问题。但我知道你想学习分而治之。

对我来说，这不是一个用 Divide Conquer 解决的好问题。

递归建议的@WillemVanOnsem 与线性遍历时的效果基本相同。

但是，如果您确实想以分而治之的方式进行操作，则需要考虑穿过中点的子字符串，即 start <= i <= mid < j <= end - 但这太过分了。

Answer 3

我认为解决问题的最佳方式是找到 y 之前和之后的位置，而不是 y。这样你会找到间隔的左右两端。代码我就不给你了，既然你特意问了，不是给你解决问题，只是指个方向，所以:

在一般情况下（区间长度为0）判断你拥有的项目是否是一个有效的左端或右端并且是一个区间
在非平凡的情况下，总是将集合向左和向右减半（如果项目的数量是奇数也没问题，只需将中间放在某个地方）并为它们进行分而治之
在非平凡的情况下，总是考虑左右子问题给你的最佳区间
在重要的情况下，请确保如果间隔恰好从左侧开始并在右侧结束，您会考虑到这一点
从这样的区间来看，长度越大越好

为了实现您想要的分而治之，您需要采用这些想法。编码愉快！

Answer 4

现在我真的有时间研究了，我决定回到这个问题并想出一个非常可读的解决方案。这是：

def across(string, start, end, middle):
    startL = middle
    bestL = ''
    while(startL >= start and string[startL] != 'y'):
        bestL = string[startL] + bestL
        startL -= 1
    startR = middle + 1
    bestR = ''
    while(startR <= end and string[startR] != 'y'):
        bestR = bestR + string[startR]
        startR += 1
    return bestL + bestR

def longestNoY(string, start, end):
    if(start > end):
        return ''
    if(start == end):
        if(string[start] == 'y'):
            return ''
        return string[start]
    middle = (start + end) // 2
    leftString = longestNoY(string, start, middle)
    rightString = longestNoY(string, middle + 1, end)
    acrossString = across(string, start, end, middle)
    return max(leftString, rightString, acrossString, key=len)

没有 Y 分而治之的最长子串

Longest Substring with no Y Divide and Conquer

algorithm

divide-and-conquer

longest-substring