707627. Find and Replace in String
Find and Replace in String
Slug: find-an-replace-in-string
Difficulty: Medium
Topic Tags: Strings, Data Structures
Company Tags: Google
Summary
The problem involves finding and replacing specific characters or substrings within a given string. This task requires a deep understanding of string manipulation techniques and algorithmic approaches to achieve the desired outcome efficiently.
Detailed Explanation
To solve this problem, we'll employ a straightforward approach using two pointers technique. We'll iterate through the input string, comparing each character with the target substring. When a match is found, we'll replace the matched characters with the replacement string. Here's a step-by-step breakdown:
- Initialize two pointers:
ifor the input string andjfor the replacement string. - Iterate through the input string using
i. - Compare the character at index
iin the input string with the character at indexjin the replacement string. - If a match is found, replace the matched characters (from index
itoi + j) in the input string with the replacement string. - Increment both pointers (
iandj) until the end of either the input string or the replacement string is reached.
Time Complexity: O(n), where n is the length of the input string, as we're iterating through the entire string once.
Space Complexity: O(1), since we're not using any additional space that scales with the input size.
Here's an ASCII art diagram illustrating the algorithm:
input | i | 0 1 2 3 4 5
| j | 1 2 3
replace | 0 1 2 3
iteration: i = 0, j = 0 (match)
replace "a" with "1"
new input | i | 1 2 3 4 5
| j | 1 2
replace | 1 2
iteration: i = 1, j = 1 (match)
replace "b" with "2"
new input | i | 2 3 4 5
| j |
replace |
...
Optimized Solutions
Java
public String findAndReplace(String input, String target, String replacement) {
int i = 0;
while (i < input.length()) {
int j = 0;
while (j < target.length() && i + j < input.length() && input.charAt(i + j) == target.charAt(j)) {
j++;
}
if (j == target.length()) {
input = input.substring(0, i) + replacement + input.substring(i + j);
i += replacement.length();
} else {
i++;
}
}
return input;
}