Рекурсивная функция, которая идентифицирует, содержится ли строка 1 в строке 2? (Python 3.4)

Question

Есть ли способ написать рекурсивную () функцию), которая принимает две строки в качестве параметров и возвращает значение True, если все символы в первой строке могут быть найдены по порядку во второй строке; и False в противном случае?

Например:

>>> contains("lit", "litter") 
True 
>>> contains("thot", "thurtle") 
False 
>>> contains("ratchet", "ramtbunchiousest") 
True 
>>> contains("shade", "hadsazie") 
False 

Буквы не должны быть последовательными (как в третьем примере), но они должны быть в порядке (поэтому четвертый пример не получится).

Я написал этот код:

def contains_recursive(s1, s2): 

if s1 == "": 
    return True 
elif s1[0] == s2[0]: 
    return contains_recursive(s1[1:], s2[1:]) 
elif s1[0] != s2[0]: 
    return contains_recursive(s1[0], s2[1:]) 
else: 
    return False 

return contains_recursive(s1, s2) == True 

и выдал эту ошибку:

IndexError: string index out of range 

Что я должен сделать, чтобы исправить эту проблему?

Answer 1

На линии:

return contains_recursive(s1[0], s2[1:]) 

вы укорочение s1 один символ, а затем при следующем вызове вы можете нажать:

return contains_recursive(s1[1:], s2[1:]) 

с s1 строки Len 1.

Вам необходимо использовать:

return contains_recursive(s1, s2[1:]) 

и добавить проверку на длину s1

Answer 2

Избегайте использования функций rescurive для повышения эффективности.

def test(s1, s2): 
    idx2 = 0 
    for c in s1: 
     if c in s2[idx2:]: 
      idx2 = s2.index(c) + 1 
     else: 
      return False 

    return True 

# Test 
lists = [ ("lit", "litter"), 
      ("thot", "thurtle"), 
      ("ratchet", "ramtbunchiousest"), 
      ("shade", "hadsazie")] 

result = [test(*t) for t in lists] 
print(result) 
# Output 
[True, False, True, False] 

Answer 3

ли я считать, что, будучи рекурсивный является обязательным требованием. В этом случае:

def contains(s1, s2): 
    if not s1: 
     return True 
    i = s2.find(s1[0]) 
    if i == -1: 
     return False 
    else: 
     return contains(s1[1:], s2[i+1:]) 

Это дает:

>>> contains("lit", "litter") 
True 
>>> contains("thot", "thurtle") 
False 
>>> contains("ratchet", "ramtbunchiousest") 
True 
>>> contains("shade", "hadsazie") 
False 

Answer 4

ошибку вы получаете может быть потому, что s2 является пустой строкой. Добавьте чек для его длины. Если вы достигнете этого момента, это означает, что вы не нашли все буквы, которые ищете, и поэтому конечный результат должен быть ложным.

if s2 == '': 
    return False