Python递归通过滑动窗口拆分字符串

Question

最近，我面临一个有趣的编码任务，它涉及到将字符串拆分为具有给定K-极限大小的多个置换

例如：

s = "iamfoobar"
k = 4  # the max number of the items on a list after the split

s可以分为以下组合

[
    ["i", "a", "m", "foobar"],
    ["ia", "m", "f", "oobar"],
    ["iam", "f", "o", "obar"]
# etc
]

我试图用一个快速递归函数来解决这个问题，但我无法让它工作

我已经试过了，但似乎不起作用

def sliding(s, k):
    if len(s) < k:
        return []
    else:
        for i in range(0, k):
            return [s[i:i+1]] + sliding(s[i+1:len(s) - i], k)

print(sliding("iamfoobar", 4))

只有这个

['i', 'a', 'm', 'f', 'o', 'o']

Answer 1

实现中的主要问题是，当循环返回第一个结果而不是附加结果时，它没有执行应该执行的操作

下面是一个实现示例：

def sliding(s, k):
    # If there is not enough values of k is below 0
    # there is no combination possible
    if len(s) < k or k < 1:
        return []

    # If k is one, we return a list containing all the combinations,
    # which is a single list containing the string
    if k == 1:
        return [[s]]

    results = []
    # Iterate through all the possible values for the first value
    for i in range(1, len(s) - k + 2):
        first_value = s[:i]
        # Append the result of the sub call to the first values
        for sub_result in sliding(s[i:], k - 1):
            results.append([first_value] + sub_result)

    return results

print(sliding("iamfoobar", 4))

Answer 2

第一个主要问题是，尽管使用循环，但会立即返回单个列表。因此，无论你如何处理周围的一切，你的输出永远不会符合你的预期，因为它将是。。。。一张单子

第二，在递归调用中，您以s[i:i+1]开始，但根据您的示例，您需要所有前缀，因此类似s[:i]的东西更合适

另外，在递归调用中，您永远不会减少k，这是自然的递归步骤

最后，您的停止条件似乎也不正确。如上所述，如果自然步骤是减少k，则自然停止将是if k == 1，然后是return [[s]]。这是因为将字符串拆分为一部分的唯一方法是字符串本身

---

重要的是要记住最终的输出格式，并考虑如何在步骤中使用它。在这种情况下，您希望以列表的形式返回所有可能排列的列表。因此，在k == 1的情况下，只需返回一个字符串列表

现在，作为步骤，您希望每次使用不同的前缀，并使用k-1将字符串其余部分的调用中的所有排列添加到前缀中。总而言之，代码可以是这样的：

def splt(s, k):
    if k == 1:  # base sace - stop condition
        return [[s]]

    res = []
    # loop over all prefixes
    for i in range(1, len(s)-k+2):
        for tmp in splt(s[i:], k-1):
            # add to prefix all permutations of k-1 parts of the rest of s
            res.append([s[:i]] + tmp)
    return res

您可以在一些输入上测试它，看看它是如何工作的

---

如果不限于递归，另一种方法是使用^{}。您可以使用它在字符串中创建所有索引组合，将其拆分为k部分，然后简单地连接这些部分并将它们放入列表中。原始版本类似于：

from itertools import combinations

def splt(s, k):
    res = []
    for indexes in combinations(range(1, len(s)), k-1):
        indexes = [0] + list(indexes) + [len(s)] # add the edges to k-1 indexes to create k parts
        res.append([s[start:end] for start, end in zip(indexes[:-1], indexes[1:])]) # concatenate the k parts

    return res