833. Find And Replace in String
Problem Description
In this problem, you are given a string s
and tasked with performing a series of replacement operations on it. These operations are specified by three parallel arrays indices
, sources
, and targets
, each of length k
, representing the k
operations.
For each operation i
:
- You have to check if the substring
sources[i]
is found in the strings
exactly at the positionindices[i]
. - If the substring
sources[i]
does not exist at the specified index, you do nothing for that particular operation. - If the substring is found, you replace it with the string
targets[i]
.
All the replacements are to be done simultaneously, which means:
- They don't affect each other's indexing (you should consider the original indices while replacing).
- There will be no overlap among the replacements (no two substrings
sources[i]
andsources[j]
will replace parts ofs
that overlap).
A substring is defined as a sequence of characters that are contiguous in a string.
Intuition
The key insight for solving this problem is understanding that all replacements happen independently and simultaneously, based on the original string s
. This calls for a mapping from each indices[i]
to its corresponding replacement (if valid), without disturbing the original indexing as subsequent replacements are planned according to the original positions.
We approach the solution by creating a mapping, in this case using an array d
with the same length as the string s
, and initialize it with a default value indicating an index with no operation. This array d
is filled with the operation index k
at position indices[i]
only if the substring sources[i]
is verified to be at the original position indices[i]
in s
.
While constructing the result:
- We iterate through the original string
s
. - At each index
i
, we check the mapping arrayd
. - If there is no replacement to be done (indicated by a default value), we simply add the current character
s[i]
to the result. - If a replacement is needed, we append the corresponding target string
targets[d[i]]
instead and incrementi
by the length of the source substring, effectively skipping over the entire substring that has been replaced. - We do this until we have processed the entire string.
By following this strategy, we can ensure that all replacements are based on the original indices, thereby meeting the constraint that the replacements do not alter each other's indexing, finally returning the correct modified string.
Learn more about Sorting patterns.
Solution Approach
The implementation of the solution follows a fairly straightforward process that can be broken down into the following steps:
-
Initialize an array
d
with the same length as the strings
which contains default values (-1
in this case). This array serves as a direct mapping to check if there's a valid replacement operation for each index in the strings
. -
Iterate over pairs of
indices
andsources
using theenumerate
function to keep track of the operation indexk
. -
For each pair
(i, src)
, uses.startswith(src, i)
to check if the substringsrc
exists starting exactly at indexi
in the strings
. If it does exist, setd[i]
tok
indicating that a replacement operation is mapped to this index. -
Create an empty list
ans
to store the characters (and substrings) that will make up the resulting string after all operations have been performed. -
Iterate over the string
s
with indexi
. Ifi
is marked ind
as a valid replacement index (d[i] != -1
), append the correspondingtargets[d[i]]
toans
. Then incrementi
by the length ofsources[d[i]]
since you've just processed the entire substring that's been replaced. -
If
i
is marked as having no operation (d[i] == -1
), simply adds[i]
toans
and incrementi
by 1 to continue processing the string. -
Once the iteration is complete, combine the contents of
ans
using"".join(ans)
to get the final string which reflects the result after applying all the replacement operations.
The data structure used in this approach is primarily an array (d
) for mapping operations. The algorithm leverages the fact that operations are independent and simultaneous, which simplifies to updating indices directly without considering the impact of previous replacementsāa classic case of 'direct addressing' where each index corresponds to a particular bit of information (here, the presence and index of a replacement operation).
The Python startswith
method is used for string comparison to verify occurrences of substrings which is crucial for determining valid operations. The use of this method avoids writing additional code to manually compare substring characters.
The iteration over the string is done in a single pass, and the list ans
builds up the result in a dynamic fashion, making the solution efficient in terms of both time and space complexity.
Overall, this approach capitalizes on the simultaneous nature of the operations and utilizes efficient string methods and direct mapping techniques provided by the language to achieve the desired outcome.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example to illustrate the solution approach.
Suppose we have the string s
which is "abcd"
and we want to perform the following operations:
indices
: [0, 2]sources
: ["a", "cd"]targets
: ["z", "x"]
This corresponds to two operations:
- Replace the substring "a" at index 0 with "z".
- Replace the substring "cd" at index 2 with "x".
Step 1: Initialize the array d
of the same length as s
(4
in this example) with default values -1
.
d
: [-1, -1, -1, -1]
Step 2: Iterate over pairs of indices
and sources
(enumerate
is not needed here since we're only doing a 1-to-1 mapping).
Checking Operation 1:
- We check if
s.startswith("a", 0)
, which isTrue
. - Thus, we set
d[0]
to the operation index0
(since 0 is the first index inindices
).
d
: [0, -1, -1, -1]
Checking Operation 2:
- We check if
s.startswith("cd", 2)
, which isTrue
. - Thus, we set
d[2]
to the operation index1
(since 1 is the second index inindices
).
d
: [0, -1, 1, -1]
Step 3: Create an empty list ans
.
ans
: []
Step 4: Iterate over the string s
with index i
.
i = 0
: Sinced[0]
is0
, we appendtargets[0]
("z") toans
and skip to the index after the replaced substring (since "a" has length1
, we incrementi
by1
).
ans
: ["z"]
i = 1
: Sinced[1]
is-1
, there's no operation. We adds[1]
("b") toans
and incrementi
by1
.
ans
: ["z", "b"]
i = 2
: Sinced[2]
is1
, we appendtargets[1]
("x") toans
and skip to the index after the replaced substring (since "cd" has length2
, we incrementi
by2
.
ans
: ["z", "b", "x"]
- Since we've reached the end of string
s
, the iteration stops.
Step 5: Combine the list ans
into the final string.
Result: "zbx"
And that's the final string after performing all the replacement operations. The algorithm efficiently applies replacements based on the original string, resulting in the desired output.
Solution Implementation
1class Solution:
2 def findReplaceString(self, s: str, indices: list[int], sources: list[str], targets: list[str]) -> str:
3 # Initialize the length of the original string.
4 length_of_string = len(s)
5
6 # Create a list to keep track of valid source index matches (-1 means no match).
7 match_tracker = [-1] * length_of_string
8
9 # Loop through indices and sources to fill the match_tracker with correct target indices.
10 for idx, (index, source) in enumerate(zip(indices, sources)):
11 # Check if the source matches the substring in s starting at index.
12 if s.startswith(source, index):
13 match_tracker[index] = idx
14
15 # Create a list to construct the answer.
16 answer_components = []
17
18 # Initialize the index for traversing the string.
19 i = 0
20 while i < length_of_string:
21 # If there's a valid source match at current index, replace with target string.
22 if match_tracker[i] != -1:
23 answer_components.append(targets[match_tracker[i]])
24 # Skip the length of the source that was replaced.
25 i += len(sources[match_tracker[i]])
26 else:
27 # If no valid source match, keep the original character.
28 answer_components.append(s[i])
29 # Move to the next character.
30 i += 1
31
32 # Join all components to form the final string and return it.
33 return "".join(answer_components)
34
1class Solution {
2
3 // Method to replace substrings in 's' according to indices 'indices', with replacements from 'targets'
4 public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
5 // Find the length of the string 's'
6 int lengthOfString = s.length();
7 // Array to keep track of the valid replacement indices
8 int[] replacementIndices = new int[lengthOfString];
9 // Initialize the replacementIndices array with -1 indicating no replacement initially
10 Arrays.fill(replacementIndices, -1);
11
12 // Loop through indices to find valid replacements
13 for (int index = 0; index < indices.length; ++index) {
14 int replaceAt = indices[index];
15 // Check if the current source string is present in 's' starting at the index 'replaceAt'
16 if (s.startsWith(sources[index], replaceAt)) {
17 // Mark the valid replacement index
18 replacementIndices[replaceAt] = index;
19 }
20 }
21
22 // Using StringBuilder for efficient string manipulation
23 StringBuilder resultBuilder = new StringBuilder();
24
25 // Iterate through the original string 's'
26 for (int i = 0; i < lengthOfString;) {
27 // If there is a valid replacement at the current index 'i'
28 if (replacementIndices[i] >= 0) {
29 // Append the target replacement string to resultBuilder
30 resultBuilder.append(targets[replacementIndices[i]]);
31 // Increment 'i' by the length of the source at this valid index to skip replaced part
32 i += sources[replacementIndices[i]].length();
33 } else {
34 // No valid replacement, append the current character and move to the next
35 resultBuilder.append(s.charAt(i++));
36 }
37 }
38 // Convert the StringBuilder object to a String before returning
39 return resultBuilder.toString();
40 }
41}
42
1class Solution {
2public:
3 // Method to perform find and replace in a string given specific indices, sources, and targets.
4 string findReplaceString(string str, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
5 int strSize = str.size();
6 // Create a lookup array to associate indices in the main string with their replacement index, initialized as -1.
7 vector<int> replacementIndex(strSize, -1);
8
9 // Loop through each index provided to calculate the replacement index.
10 for (int i = 0; i < indices.size(); ++i) {
11 int index = indices[i];
12 // Only set the replacement index if the source matches the substring starting at index.
13 if (str.compare(index, sources[i].size(), sources[i]) == 0) {
14 replacementIndex[index] = i;
15 }
16 }
17
18 string result; // Initialize the result string which will accumulate the final output.
19
20 // Iterate through the original string by character.
21 for (int i = 0; i < strSize;) {
22 // If the current index has a valid replacement index, concatenate the target string.
23 if (replacementIndex[i] != -1) {
24 result += targets[replacementIndex[i]];
25 // Move the index forward by the length of the source that was replaced.
26 i += sources[replacementIndex[i]].size();
27 } else {
28 // If there's no replacement, just append the current character to the result.
29 result += str[i++];
30 }
31 }
32
33 // Return the modified string after all replacements are done.
34 return result;
35 }
36};
37
1function findReplaceString(
2 originalString: string,
3 indexArray: number[],
4 sourceArray: string[],
5 targetArray: string[],
6): string {
7 // The length of the original string.
8 const stringLength: number = originalString.length;
9
10 // An array to keep track of which indices in the original string have valid replacements.
11 const replacementIndexArray: number[] = Array(stringLength).fill(-1);
12
13 // Iterate through the array of indices to find valid replacements.
14 for (let i = 0; i < indexArray.length; ++i) {
15 const index = indexArray[i];
16 const source = sourceArray[i];
17
18 // If the source string is found at the specified index, update the replacement index array.
19 if (originalString.startsWith(source, index)) {
20 replacementIndexArray[index] = i;
21 }
22 }
23
24 // An array to build the new string with replacements.
25 const resultArray: string[] = [];
26
27 // Iterate through the original string while applying replacements.
28 let currentIndex = 0;
29 while (currentIndex < stringLength) {
30 // If there is a valid replacement at the current index, add the target string to the result array.
31 if (replacementIndexArray[currentIndex] >= 0) {
32 const replacementIndex = replacementIndexArray[currentIndex];
33 resultArray.push(targetArray[replacementIndex]);
34
35 // Move the current index ahead by the length of the source string that was replaced.
36 currentIndex += sourceArray[replacementIndex].length;
37 } else {
38 // Otherwise, add the current character to the result array and move to the next character.
39 resultArray.push(originalString[currentIndex++]);
40 }
41 }
42
43 // Join the result array into a single string and return it.
44 return resultArray.join('');
45}
46
Time and Space Complexity
The given Python code snippet is designed to replace parts of a string s
with alternate strings provided in the targets
list. The replacements are conditional on the substrings in s
starting at indices found in indices
matching the corresponding strings in sources
. Here is the computational complexity analysis of the code:
Time Complexity
The time complexity of the function is determined by several operations:
-
Iterating Over
indices
andsources
: There is an initial loop that iterates through the zippedindices
andsources
. This takesO(m)
time, wherem
is the number of elements inindices
(and alsosources
andtargets
). -
String Matching with
startswith
: Inside the loop, there is a call to thestartswith
function. This has a worst-case time complexity ofO(len(src))
for each invocation, which can be up toO(n)
in the worst case (wheren
is the length of the strings
). Therefore, in the worst case, this part of the loop could have a time complexity ofO(m * n)
. -
Building the Result String: After the initial loop, the function iterates through string
s
and constructs the answer. In the worst case, each character could potentially be copied individually (when there are no matches), resulting in a time complexity ofO(n)
. -
Appending to the
ans
List and Join Operation: The append operation isO(1)
for each character or replacement string, but thejoin
operation at the end isO(n)
since it iterates over the entire list of characters and concatenates them into a new string.
Considering these parts together, the total time complexity is the sum of the complexities of these steps, which is O(m * n) + O(n) + O(n)
. O(m * n)
is likely the dominating term here, so the overall time complexity can be considered O(m * n)
.
Space Complexity
The space complexity of the function is determined by the additional memory space used, apart from the input. The main extra storage used is:
-
Array
d
: The arrayd
has the same length as the input strings
, i.e.,O(n)
. -
List
ans
: The listans
is used to construct the resulting string. In the worst case, it could holdn
characters plus the length of alltargets
strings if every source is found and replaced. Assuming the sum of the lengths of alltargets
ist
, the space used byans
could be up toO(n + t)
.
Therefore, the overall space complexity is the largest of the space used by d
and ans
, leading to a total complexity of O(n + t)
since t
can be larger than n
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!