首頁猿問 Python遞歸通過滑動窗口拆分字符串

Python遞歸通過滑動窗口拆分字符串

Python

慕田峪4524236 2022-12-14 20:56:58

最近，我遇到了一個有趣的編碼任務，涉及將字符串拆分為具有給定 K 限制大小的多個排列。例如：s = "iamfoobar"k = 4 # the max number of the items on a list after the splits可以拆分為以下組合[ ["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']

查看完整描述

2 回答

HUX布斯

TA貢獻1876條經驗獲得超6個贊

您的第一個主要問題是，盡管您使用循環，但您會立即返回一個列表。因此，無論您如何修復周圍的一切，您的輸出都永遠不會符合您的預期……一個列表。

其次，在您開始的遞歸調用中，s[i:i+1]但根據您的示例，您需要所有前綴，因此s[:i]更合適。

另外，在遞歸調用中你永遠不會減少k這是自然的遞歸步驟。

最后，你的停止條件似乎也是錯誤的。如上所述，如果自然步驟減少，k則自然停止。這是因為將字符串拆分為 1 個部分的唯一方法是字符串本身......if k == 1return [[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

您可以在一些輸入上對其進行測試，看看它是如何工作的。

如果您不限于遞歸，另一種方法是使用itertools.combinations. 您可以使用它在字符串中創建所有索引組合，將其拆分為多個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

反對回復 2022-12-14

長風秋雁

TA貢獻1757條經驗獲得超7個贊

您實現中的主要問題是您的循環沒有執行預期的操作，因為它返回第一個結果而不是附加結果。

下面是一個實現示例：

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))

反對回復 2022-12-14

2 回答
0 關注
180 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

Python遞歸通過滑動窗口拆分字符串

Python遞歸通過滑動窗口拆分字符串

2 回答

添加回答