在遞歸函數中保持計數

我想弄清楚如何編寫一個遞歸函數（只有一個參數），它返回字符串中出現子字符串「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

在遞歸函數中保持計數

回答

相關問題