In this guide, you will get 833. Find And Replace in String LeetCode Solution with the best time and space complexity. The solution to Find And Replace in String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
You are given a 0-indexed string s that you must perform k replacement operations on. The replacement operations are given as three 0-indexed parallel arrays, indices, sources, and targets, all of length k.
To complete the ith replacement operation:
Check if the substring sources[i] occurs at index indices[i] in the original string s.
If it does not occur, do nothing.
Otherwise if it does occur, replace that substring with targets[i].
For example, if s = “abcd”, indices[i] = 0, sources[i] = “ab”, and targets[i] = “eee”, then the result of this replacement will be “eeecd”.
All replacement operations must occur simultaneously, meaning the replacement operations should not affect the indexing of each other. The testcases will be generated such that the replacements will not overlap.
For example, a testcase with s = “abc”, indices = [0, 1], and sources = [“ab”,”bc”] will not be generated because the “ab” and “bc” replacements overlap.
Return the resulting string after performing all replacement operations on s.
A substring is a contiguous sequence of characters in a string.
Example 1:
Input: s = “abcd”, indices = [0, 2], sources = [“a”, “cd”], targets = [“eee”, “ffff”]
Output: “eeebffff”
Explanation:
“a” occurs at index 0 in s, so we replace it with “eee”.
“cd” occurs at index 2 in s, so we replace it with “ffff”.
Example 2:
Input: s = “abcd”, indices = [0, 2], sources = [“ab”,”ec”], targets = [“eee”,”ffff”]
Output: “eeecd”
Explanation:
“ab” occurs at index 0 in s, so we replace it with “eee”.
“ec” does not occur at index 2 in s, so we do nothing.
Constraints:
1 <= s.length <= 1000
k == indices.length == sources.length == targets.length
1 <= k <= 100
0 <= indexes[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.
Complexity Analysis
Time Complexity: O(n\log n + n|\texttt{s}|), where n = |\texttt{indices}|
Space Complexity: O(n + |\texttt{s}|)
833. Find And Replace in String LeetCode Solution in C++
class Solution {
public:
string findReplaceString(string s, vector<int>& indices,
vector<string>& sources, vector<string>& targets) {
vector<pair<int, int>> sortedIndices;
for (int i = 0; i < indices.size(); ++i)
sortedIndices.emplace_back(indices[i], i);
ranges::sort(sortedIndices, greater<>());
for (const auto& [index, i] : sortedIndices) {
const string& source = sources[i];
const string& target = targets[i];
if (s.substr(index, source.length()) == source)
s = s.substr(0, index) + target + s.substr(index + source.length());
}
return s;
}
}; /* code provided by PROGIEZ */
833. Find And Replace in String LeetCode Solution in Java
class Solution {
public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
List<Pair<Integer, Integer>> sortedIndices = new ArrayList<>();
for (int i = 0; i < indices.length; ++i)
sortedIndices.add(new Pair<>(indices[i], i));
Collections.sort(sortedIndices, Comparator.comparing(Pair::getKey, Comparator.reverseOrder()));
for (Pair<Integer, Integer> sortedIndex : sortedIndices) {
final int index = sortedIndex.getKey();
final int i = sortedIndex.getValue();
final String source = sources[i];
final String target = targets[i];
if (index + source.length() <= s.length() &&
s.substring(index, index + source.length()).equals(source))
s = s.substring(0, index) + target + s.substring(index + source.length());
}
return s;
}
} // code provided by PROGIEZ
833. Find And Replace in String LeetCode Solution in Python
class Solution:
def findReplaceString(self, s: str, indexes: list[int],
sources: list[str], targets: list[str]) -> str:
for index, source, target in sorted(
zip(indexes, sources, targets),
reverse=True):
if s[index:index + len(source)] == source:
s = s[:index] + target + s[index + len(source):]
return s # code by PROGIEZ
