CODEWITHSUNDEEP
stringrecursionpython-3.xsubstring
Soheil__K
Soheil__K

Reputation: 642

Using Recursion to Replace all occurences of a substring with another substring

Given an string and two of its substrings (named a and b) I need to write a recursive function that replace all occurrences of b with a and then returns the new string.

Could someone help me how to begin?

Upvotes: 2

Views: 5880

Answers (1)

Luca Mastrostefano
Luca Mastrostefano

Reputation: 3271

Recursively you know that your function applied to:

  • base case) An empty string, must return an empty string;
  • rec case) A string starting with b, must replace b with a and check the rest of the string;
  • rec case) Else, return the first character of the string chained to rest of the string returned recursively

Here is the algorithm:

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)

Test:

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

Output:

ok this is ok a simple ok test

Upvotes: 4

Related Questions