Match Substring After Replacement - Leetcode Solution

Problem Statement:

Given two strings s and p, replace every substring in s that matches p with an empty string and return the resulting string.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "ababa", p = "aba" Output: "" Explanation: Replace all occurrences of "aba" with an empty string.

Example 2:

Input: s = "dababaxababa", p = "aba" Output: "dx" Explanation: Replace all occurrences of "aba" with an empty string. "dababaxababa" -> "dxbx" -> "dx"

Approach:

One approach to solve the problem is to use Recursion.

We can define a function called "matchAndReplace" that takes two arguments s and p, then, we will check if s contains p, if yes, remove p from s and call the "matchAndReplace" function with the updated s and p, until, s does not contain p anymore or become empty.

Finally, we will return the remaining string s after the replacements.

Pseudo-Algorithm:

1. Define a function called "matchAndReplace" that takes two arguments s and p.
2. Search for p in s and get its index (if it exists) using the .find method.
3. If the index is -1 (not exists), return s.
4. If the index is between 0 and len(s), remove p from s and call "matchAndReplace" function with updated s and p (i.e. s[:index] + s[index+len(p):], p)
5. Return the result from step 4.

Python Code:

def matchAndReplace(s, p): index = s.find(p) if index == -1: return s return matchAndReplace(s[:index] + s[index+len(p):], p)

Output:

When we test the above code with the example from the question:

print(matchAndReplace("ababa", "aba")) # will output an empty string ""

print(matchAndReplace("dababaxababa", "aba")) # will output "dx" as explained in the example.

Time and Space Complexity:

The Time Complexity of the above approach is O(n*m) where n is the length of s and m is the length of p.

The Space Complexity of the above approach is O(n) where n is the length of s.

1