时间戳

首页 > 解决方案 > k个连续字符串中最长的

python - k个连续字符串中最长的

问题描述

我正在定义一个 Python 函数来确定最长的字符串，如果原始字符串针对每 k 个连续字符串进行组合。该函数有两个参数，strarr和k。

这是一个例子：

max_consec(["zone", "abigail", "theta", "form", "libe", "zas", "theta", "abigail"], 2) --> "abigailtheta"

到目前为止，这是我的代码（本能是我没有k在函数中正确传递）

def max_consec(strarr, k):
    lenList = []
    for value in zip(strarr, strarr[k:]):
        consecStrings = ''.join(value)
        lenList.append(consecStrings)
    for word in lenList: 
        if max(word):
            return word

这是一个未通过的测试用例：

testing(longest_consec(["zone", "abigail", "theta", "form", "libe", "zas"], 2), "abigailtheta")

我的输出：

'zonetheta' should equal 'abigailtheta'

标签： pythonstringfunction

解决方案

将字符串长度存储在数组中。现在假设一个大小为 k 的窗口通过这个列表。跟踪此窗口中的总和和窗口的起点。

当窗口到达数组的末尾时，您应该有最大的总和和出现最大值的索引。使用此窗口中的元素构造结果。

时间复杂度：O(数组大小+所有字符串大小之和)~O(n)

还添加一些极端情况处理 whenk > array_size或k <= 0

def max_consec(strarr, k):

    size = len(strarr)

    # corner cases
    if k > size or k <= 0:
        return "None"  # or None

    # store lengths
    lenList = [len(word) for word in strarr]

    print(lenList)

    max_sum = sum(lenList[:k])   # window at index 0
    prev_sum = max_sum
    max_index = 0

    for i in range(1, size - k + 1):
        length = prev_sum - lenList[i-1] + lenList[i + k - 1]  # window sum at i'th index. Subract previous sum and add next sum
        prev_sum = length

        if length > max_sum:
            max_sum = length
            max_index = i

    return "".join(strarr[max_index:max_index+k])  # join strings in the max sum window


word = max_consec(["zone", "abigail", "theta", "form", "libe", "zas", "theta", "abigail"], 2)

print(word)

推荐阅读