时间戳

首页 > 解决方案 > 需要减少此函数中的递归调用次数

python - 需要减少此函数中的递归调用次数

问题描述

问题是给定一个字符串 S 和一个整数 k<len(S)，我们需要在字典顺序中找到最高的字符串，删除任何 k 个字符，但保持字符串的相对顺序。

这是我到目前为止所拥有的：

def allPossibleCombinations(k,s,strings):
    if k == 0:
       
        strings.append(s)
        return strings
    
    for i in range(len(s)):
        new_str = s[:i]+s[i+1:]
        strings = allPossibleCombinations(k-1, new_str, strings)
        
    return strings

def stringReduction(k, s):
    strings = []
    combs = allPossibleCombinations(k,s, strings)
    return sorted(combs)[-1]

这适用于一些测试用例，但它说我对其他测试用例有太多递归调用。我不知道测试用例。

标签： pythonstringrecursion

解决方案

这应该让你开始 -

from itertools import combinations

def all_possible_combinations(k = 0, s = ""):
  yield from combinations(s, len(s) - k)

现在，对于给定的k=2, 和s="abcde"，我们显示所有删除字符s的组合 -k

for c in all_possible_combinations(2, "abcde"):
  print("".join(c))

# abc
# abd
# abe
# acd
# ace
# ade
# bcd
# bce
# bde
# cde

推荐阅读