Использование рекурсии для замены всех вхождений подстроки на другую подстроку

Question

Учитывая строку и две ее подстроки (с именем a и b), мне нужно написать рекурсивную функцию, которая заменяет все вхождения b на a, а затем возвращает новую строку ,

Не мог бы кто-нибудь помочь мне с чего начать?

Answer 1

Рекурсивный вы знаете, что ваша функция применяется:

• базовый вариант) пустая строка должна возвращать пустую строку;
• case case) Строка, начинающаяся с b, должна заменить b на a и проверить остальную часть строки;
• прна случая) В противном случае, вернуть первый символ строки, прикованной к остальной части строки возвращается рекурсивно

Вот алгоритм:

def rec_replace(string, a, b): 
    if not string: #if the string is empty 
     return "" 
    elif string[:len(b)] == b: #if the string start with b, replace it with a 
     return a + rec_replace(string[len(b):], a, b) 
    else: #else, add this character and go to the next one 
     return string[0] + rec_replace(string[1:], a, b) 

Тест:

print rec_replace("hello this is hello a simple hello test", "ok", "hello") 

Выход:

ok this is ok a simple ok test