Leetcode 833: Find And Replace in String
You are given a string s and k replacement operations. Each replacement operation consists of an index, a source substring, and a target substring. For each operation, check if the source substring occurs at the given index in s. If it does, replace the substring with the target. All operations are performed simultaneously, meaning they do not affect each other’s indexing. The task is to return the modified string after all operations are applied.
Problem
Approach
Steps
Complexity
Input: The input consists of a string s and three arrays: indices, sources, and targets. Each element in indices represents the starting position of a source substring in s, and each corresponding element in sources is the substring to replace. The corresponding element in targets is the substring to replace sources with.
Example: Input: s = 'hello', indices = [0, 3], sources = ['he', 'lo'], targets = ['hi', 'ya']
Constraints:
• 1 <= s.length <= 1000
• k == indices.length == sources.length == targets.length
• 1 <= k <= 100
• 0 <= indices[i] < s.length
• 1 <= sources[i].length, targets[i].length <= 50
• s consists of only lowercase English letters
• sources[i] and targets[i] consist of only lowercase English letters
Output: The output is the modified string after performing all replacement operations on s simultaneously.
Example: Output: 'hiya'
Constraints:
• The result should be the string after all replacements have been applied, without affecting the indexing of subsequent replacements.
Goal: The goal is to apply all k replacements to the string s and return the final modified string. Each replacement should be checked, and if the source substring matches at the specified index, it should be replaced by the target substring.
Steps:
• Step 1: Create a list of index-source-target triples to store the replacement operations.
• Step 2: Sort the replacement operations in descending order of their indices to ensure replacements do not interfere with each other.
• Step 3: For each operation, check if the source substring matches the substring at the given index in s. If it does, replace it with the target.
• Step 4: Return the final string after all replacements have been applied.
Goal: Ensure that the replacement operations do not overlap, and that each operation is applied only if the source substring matches at the specified index in the original string.
Steps:
• The replacement operations are guaranteed to not overlap.
Assumptions:
• The input string s and the replacement arrays are valid according to the constraints.
• Input: Input: s = 'hello', indices = [0, 3], sources = ['he', 'lo'], targets = ['hi', 'ya']
• Explanation: In this example, 'he' at index 0 is replaced by 'hi', and 'lo' at index 3 is replaced by 'ya', resulting in the string 'hiya'.
• Input: Input: s = 'abcd', indices = [0, 2], sources = ['a', 'cd'], targets = ['eee', 'ffff']
• Explanation: Here, 'a' at index 0 is replaced by 'eee', and 'cd' at index 2 is replaced by 'ffff', resulting in 'eeebffff'.
Approach: To solve this problem, we need to apply each replacement operation in such a way that no two replacements interfere with each other. This can be done by sorting the replacement operations in descending order of their indices and performing the replacements sequentially.
Observations:
• We need to ensure that replacements are applied without changing the index positions of subsequent operations.
• Sorting the operations by their indices in descending order will allow us to apply the replacements from the end of the string to the beginning, preventing overlap.
Steps:
• Step 1: Parse the input and create a list of tuples containing the index, source, and target.
• Step 2: Sort the list of operations in descending order of indices to prevent affecting subsequent replacements.
• Step 3: For each replacement operation, check if the source matches the substring at the specified index. If it does, replace it with the target.
• Step 4: Return the modified string after all replacements have been applied.
Empty Inputs:
• An empty string for s or empty arrays for indices, sources, or targets should not occur as per the problem constraints.
Large Inputs:
• The solution should handle large inputs where s has up to 1000 characters and k is up to 100.
Special Values:
• Ensure that all source substrings are non-overlapping and fit within the string boundaries.
Constraints:
• The solution should efficiently handle the maximum input size.
string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
/*
string s
indices - arr of int
src arr of str
tgt arr of str
*/
vector<pair<int, int>> ind;
for(int i = 0; i < indices.size(); i++)
ind.push_back({indices[i], i});
sort(ind.rbegin(), ind.rend());
for(auto it: ind) {
string src = sources[it.second], tgt = targets[it.second];
if(s.substr(it.first, src.size()) == src)
s = s.substr(0, it.first) + tgt + s.substr(it.first+ src.size());
}
return s;
}
1 : Function Definition
string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
Define the function 'findReplaceString' which takes four arguments: a string 's' and vectors for indices, source substrings, and target replacements.
2 : Parameter Declaration
string s
Declares the string variable 's' that will be processed.
3 : Variable Declaration
vector<pair<int, int>> ind;
Declares a vector 'ind' to store pairs of indices and their respective positions for sorting.
4 : For Loop
for(int i = 0; i < indices.size(); i++)
Iterates over the 'indices' vector to process each index and associate it with its position.
5 : Push to Vector
ind.push_back({indices[i], i});
Pushes the pair of index and its position into the 'ind' vector for sorting.
6 : Sort
sort(ind.rbegin(), ind.rend());
Sorts the 'ind' vector in reverse order to ensure replacements happen from the end of the string.
7 : For Loop
for(auto it: ind) {
Iterates over the sorted pairs of indices to perform replacements in the string.
8 : String Manipulation
string src = sources[it.second], tgt = targets[it.second];
Extracts the corresponding source and target strings based on the current index.
9 : Conditional Check
if(s.substr(it.first, src.size()) == src)
Checks if the substring of 's' at the current position matches the source string.
10 : String Replacement
s = s.substr(0, it.first) + tgt + s.substr(it.first+ src.size());
Performs the replacement of the source substring with the target string.
11 : Return Statement
return s;
Returns the modified string after all replacements.
Best Case: O(k log k + n), where k is the number of replacement operations and n is the length of the string s.
Average Case: O(k log k + n), where k is the number of operations and n is the length of the string.
Worst Case: O(k log k + n), which occurs when all operations need to be checked and applied to the entire string.
Description: The time complexity is dominated by the sorting of the operations, followed by the sequential replacement checks.
Best Case: O(k), if no additional space is required beyond the input data.
Worst Case: O(k), as we store the indices, sources, and targets in arrays, which are of size k.
Description: The space complexity is primarily determined by the storage of the replacement operations.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus