在递归函数中保持计数

我想弄清楚如何编写一个递归函数（只有一个参数），它返回字符串中出现子字符串“ou”的次数。我感到困惑的是，我不允许使用除len之外的任何内置字符串函数，或字符串运算符[]和[：]进行索引和拼接。所以我不能使用发现内置的查找功能在递归函数中保持计数

我记得看到这样的事情，但它使用两个参数，它也使用find（）方法

def count_it(target, key): 
    index = target.find(key) 
    if index >= 0: 
    return 1 + count_it(target[index+len(key):], key) 
    else: 
    return 0

来源

2011-11-01 Will S

什么类型的可的说法呢？你被允许传入一个元组吗？ –

非常低效的，但应工作：

def count_it(target): 
    if len(target) < 2: 
     return 0 
    else: 
     return (target[:2] == 'ou') + count_it(target[1:])

看到它联机工作：ideone

它基本上是相同的想法，你发布的代码，但它只能移动一个字符在一次通过字符串，而不是使用find跳转到下一场比赛。

来源

2011-11-01 20:24:48

它的工作原理！我只是一个初学者，但你为什么会说它效率低下？ –

@ Will S：主要问题是'x [1：]'需要复制整个字符串（除了第一个字符）。这给出了O（n * n）的复杂性。 –

试试这个，它适用于一般情况下（键的任何价值，不仅“OU”）：

def count_it(target, key): 
    if len(target) < len(key): 
     return 0 
    found = True 
    for i in xrange(len(key)): 
     if target[i] != key[i]: 
      found = False 
      break 
    if found: 
     return 1 + count_it(target[len(key):], key) 
    else: 
     return count_it(target[1:], key)

来源

2011-11-01 20:42:41

在递归函数中保持计数

回答

相关问题