最长的k个连续字符串

问题描述 投票:1回答:4

我正在定义一个Python函数来确定最长的字符串,如果每个k个连续字符串组合原始字符串。该函数有两个参数,strarrk

这是一个例子:

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'
python string function
4个回答
2
投票

我不太清楚“每k个连续字符串”是什么意思,但如果你的意思是取列表的k长度片段并连接每个片中的所有字符串,例如

['a', 'bb', 'ccc', 'dddd']  # k = 3

['a', 'bb', 'ccc']
['bb', 'ccc', 'dddd']

然后

'abbccc'
'bbcccddd'

然后这工作......

# for every item in strarr, take the k-length slice from that point and join the resulting strings
strs = [''.join(strarr[i:i + k]) for i in range(len(strarr) - k + 1)]

# find the largest by `len`gth
max(strs, key=len)

this post提供了替代方案,尽管其中一些很难阅读/冗长


1
投票

如果我正确理解你的问题。你必须消除重复值(在这种情况下使用set),按长度排序并连接k个最长的单词。

>>> def max_consec(words, k):
...   words = sorted(set(words), key=len, reverse=True)
...   return ''.join(words[:k])
...
>>> max_consec(["zone", "abigail", "theta", "form", "libe", "zas", "theta", "abigail"], 2)
'abigailtheta'

更新:如果k个元素应该是连续的。您可以创建成对的连续单词(在本例中为zip)。如果他们加入,返回时间最长。

>>> def max_consec(words, k):
...     return max((''.join(pair) for pair in zip(*[words[i:] for i in range(k)])), key=len)
...
>>> max_consec(["zone", "abigail", "theta", "form", "libe", "zas", "theta", "abigail"], 2)
'abigailtheta'

1
投票

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

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

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

k > array_sizek <= 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)

1
投票
def max_consec(strarr, k):
    n = -1
    result = ""
    for i in range(len(strarr)):
        s = ''.join(strarr[i:i+k])
        if len(s) > n:
            n = len(s)
            result = s     
    return result
  • 迭代字符串列表并创建一个新字符串,将其与下一个k字符串连接起来
  • 检查新创建的字符串是否最长。如果这样记住它
  • 重复上述步骤,直到迭代完成
  • 返回记忆的字符串
© www.soinside.com 2019 - 2024. All rights reserved.