Leetcode 833. Find And Replace in String

Problem Explanation

In the given problem, we are provided with a string S, along with arrays of indexes, sources (substrings) and targets.

The objective is to, for each replacement operation, check if the source string starts at the respective index in S. If it does, we replace that occurrence of the source string with the corresponding target string. If the source string does not start at the given index, we do not do any replacement operation.

We are also told that these operations occur simultaneously, and none of the replacement operations will overlap with each other.

The task is to return the final string after all replacement operations have been performed.

Solution Approach

A key aspect to note here is that all operations are to be performed simultaneously. Therefore, we begin by sorting the replacement operations in reverse order of the indexes. This is because, if we perform the operations from left to right, the indexes for subsequent operations could change due to replacements, which complicates our task. However, if we perform the replacements from right to left (i.e., starting from the end of the string), the indexes for the remaining operations stay unaffected.

For each operation, we:

  1. Check if the source string starts at the given index in the original string S.
  2. If it does, we replace it with the target string. If it doesn't, we move to the next operation.

Finally, we return the final string after all operations.

Solution Walkthrough

Let's take the example where S = "abcd", indexes = [0,2], sources = ["ab","cd"], targets = ["eee","ffff"].

We begin by sorting the operations in reverse order: ["cd",2,"ffff"],["ab",0,"eee"].

For the first operation, since "cd" starts at index 2 in S, we replace "cd" with "ffff". S now becomes "abffff".

For the next operation, "ab" does start at index 0, so we replace it with "eee". Now, S is "eeeffff".

Thus, "eeeffff" is our final string, which we return.

Solution Code

Python

1
2python
3class Solution:
4    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:
5        # pair each operation and reverse-sort it
6        sorted_operations = sorted(zip(indexes, sources, targets), reverse=True)
7        for i, s, t in sorted_operations:
8            # replace if source s starts at index i
9            if S[i:i+len(s)] == s:
10                S = S[:i] + t + S[i+len(s):]
11        return S

Java

1
2java
3class Solution {
4    public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
5        int n = indexes.length;
6        Replacement[] replacements = new Replacement[n];
7
8        for (int i = 0; i < n; i++)
9            replacements[i] = new Replacement(indexes[i], i);
10
11        Arrays.sort(replacements, (a, b) -> b.index - a.index);
12
13        for (Replacement replacement : replacements) {
14            int i = replacement.index;
15            int j = replacement.pointer;
16            String source = sources[j], target = targets[j];
17            if (S.substring(i, i + source.length()).equals(source))
18                S = S.substring(0, i) + target + S.substring(i + source.length());
19        }
20        return S;
21    }
22
23    class Replacement {
24        int index, pointer;
25
26        Replacement(int index, int pointer) {
27            this.index = index;
28            this.pointer = pointer;
29        }
30    }
31}

Javascript

1
2javascript
3var findReplaceString = function(S, indexes, sources, targets) {
4    let sortedOperations = indexes.map((v, i) => [v, sources[i], targets[i]])
5        .sort((a, b) => b[0] - a[0]); 
6    for (const [i, s, t] of sortedOperations) 
7        if (S.substring(i, i + s.length) === s)
8            S = S.substring(0, i) + t + S.substring(i + s.length);
9    return S;
10};

C++

1
2C++
3class Solution {
4public:
5    string findReplaceString(string S, vector<int>& indexes, vector<string>& sources, vector<string>& targets) {
6        vector<pair<int, int>> sorted_operations;
7
8        for (int i = 0; i < indexes.size(); ++i)
9            sorted_operations.push_back({indexes[i], i});
10
11        sort(sorted_operations.rbegin(), sorted_operations.rend());
12
13        for (auto& [i, j] : sorted_operations) {
14            if (S.substr(i, sources[j].size()) == sources[j])
15                S = S.substr(0, i) + targets[j] + S.substr(i + sources[j].size());
16        }
17        return S;
18    }
19};

C#

1
2C#
3public class Solution {
4    public string FindReplaceString(string S, int[] indexes, string[] sources, string[] targets) {
5        var sortedOperations = indexes
6            .Select((v, i) => new {Index = v, Source = sources[i], Target = targets[i]})
7            .OrderByDescending( x => x.Index)
8            .ToList();
9        
10        foreach(var operation in sortedOperations)
11        {
12            if (S.Substring(operation.Index, operation.Source.Length) == operation.Source)
13                S = S.Substring(0, operation.Index) + operation.Target 
14                        + S.Substring(operation.Index + operation.Source.Length);
15        }        
16        return S;
17    }
18}

Note: The C# LINQ code Select((v, i) => new {...}) generates an list of anonymous objects, where v represents individual elements in indexes array and i is the index of the element. The OrderByDescending function sorts this list in decreasing order of Index for each object.

The Java, Javascript, C++ and C# solutions follow similar principles. They first sort the operations in reverse order, where each operation is a triple of index, source and target. They then iterate over these sorted operations to check if the source string starts at the specified index and perform replacement if it does.In conclusion, our problem is resolved by first recognizing the need to perform the replacements in a certain order, which is from highest index to lowest. This allows for correct replacement as proceeding from low to high would alter the indexes of subsequent replacements.

After sorting the operations in accordance to this, we then check whether the substring corresponding to an operation matches the source string specified. If it does, a replacement with the target string follows. This is done for all operations in the right order.

At the end of all operations, we return the final resultant string.

Out solution works for Python, Java, JavaScript, C++, and C#. It's an optimal solution that solves the problem efficiently in O(n log n) time due to the sorting process, where n is the number of replacements.

Overall, this task critically tests awareness and understanding of string manipulation methods and functionalities in different programming languages, as well as the necessity for correct ordering in certain operations.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫