Question
|
Difficulty Level:
3
|
Solution
|
Explanation Quality:5
|
String manipulation questions are common and you can experience many variations
on these questions. For this question we have to make sure that we delete the given
word in a single pass of the string. More importantly we have to make sure that
we do the task in place that is we dont declare any additional memory.
Say we have the following example:
Sentence: I was going to the market.
Word to delete : the
So we are actually looking to delete the substring 'the' which is preceded by a
space and is followed either by a space, a comma, a full stop or some other punctuation
mark. For now let us forget this restriction to make the code more readable.
for(i =0; ilength_of_string; i++){
if(i+3 <= length_of_string){
if(string[i] == 't'){
if(string[i+1] == 'h'){
if(string[i+2] == 'e'){
int temp = i;
int j = i + length_of_substring;
while(j <= length_of_string){
string[i] = string[j];
i++;
j++;
}
i = temp;
length = length_of_substring;
}
}
}
}
So let's see how the code works. I intentially wrote the three if statements to
detect the substring 'the'. It's not generic but my main focus is on the algorithm
rather than the detection part. You can possibly use strcmp function or write your
own write a for loop for that.
Now once the substring is detected. We essentially jump past the substring when
we do
j = i + length_of_substring
Now, we copy the rest of the original sentence over the substring. Once we have
copied the rest of the sentence, we reset i to start scanning again because the
substring can again occur in the sentence.
You have to be careful about the test cases though. You might need additional lines
of code to take care of the following cases:
i. null sentence that is empty string
ii. sentence just containing 'the'
iii. string just containing multiple 'the'
Also note that the pseudocode that I have given assumes that there is a null string
at the end of the sentence.
|