Last Updated: 20 Feb, 2021
Encoded Letter
Moderate
Asked in company
Kevin got an encoded letter from his friend in which all occurrences of a word (say, ‘X’) is replaced by another word (say, ‘R’). This letter is very confidential and that’s why his friend directly calls him and tell him the words ‘X’ and ‘R’. But, Kevin is not able to decode the letter and so, he wants your help as he believes in you.
All you have to do is to replace all occurrences of the word ‘X’ with the word ‘R' in the given letter.
Note:
You are provided with the content written in the letter. The content of the letter will only contain the English alphabets, non-negative integers, and white spaces. It is guaranteed that the content will have the first character as the English alphabet or a non-negative integer.
Input Format:
The first line contains a single integer ’T’ representing the number of test cases.
The first line of each test case will contain the string ‘S’ which represents the content written in the given letter.
The second line of each test case will contain the string ‘X’ which represents the word ‘X’.
The third line of each test case will contain the string ‘R’ which represents the word ‘R’.
Output Format:
For each test case, return the decoded content of the given letter or we can say return the new content of the letter in which all occurrences of the word ‘X’ is replaced by the word ‘R’.
Note:
You don’t need to print anything, It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= |S| <= 10^4
1 <= |X| <= |S|
1 <= |R| <= |S|
Where '|S|', '|X|', '|R|' denotes the length of the string 'S', 'X', 'R' respectively.
Time limit: 1 sec
Approaches
The basic idea is to iterate through the content and whenever find the word ‘X’ just replace it with the word ‘R’. We will not be going to change the string that represents the content instead of that we create another string to store the decoded content.
The steps are as follows:
- Create a variable (say, ‘DECODE’) of string type to store the decoded string.
- Iterate through the given content ( say, iterator = ‘i’ )
- Check, the first character of the word ‘X’ and the character of content at ‘i’ is the same and also check ‘i’ + length of the word is less than the length of content. If these conditions are true -
- Iterate through the given content in forwarding direction from ‘i’ to ‘i’ + length of word ‘X’.
- If the complete word matches with the word ‘X’, then insert the word ‘R’ into the ‘DECODE’ string.
- Else, insert the word that appears in the content in this range.
- Else, insert the character into the ‘DECODE’ string.
- Check, the first character of the word ‘X’ and the character of content at ‘i’ is the same and also check ‘i’ + length of the word is less than the length of content. If these conditions are true -
- Return the string ‘DECODE’.
The basic idea is to create the longest proper prefix and suffix array for word ‘X’ and then apply the KMP algorithm to find the occurrences of word ‘R’ in the content.
The steps are as follows:
- Create a vector of type int named ‘LPS’ to store the longest proper prefix and suffix for each character in ‘X’.
- Create a variable named ‘LEN’ to store the number of characters that match with the word ‘X’.Initially, set ‘LEN’ = 0.
- For the first character of the word ‘X’, there is no prefix that is also a suffix so make ‘LPS[0]' = 0.
- Create a variable to point the current index in the word ‘X’. (say, variable = ‘i’).
- Iterate till ‘i’ becomes greater than or equal to ‘N’. (Initially, ‘i’ = 0)
- Check if, ‘X[ i ]’ is the same as ‘X[ ‘LEN’ ]’ then increment the ‘LEN’ by 1 and make ‘LPS[ i ]’ = ‘LEN’. Also, increment ‘i’ by 1.
- Else
- If, ‘LEN’ is 0 then make ‘LPS’[ i ] = 0 and increment ‘i’ by 1.
- Else, set ‘LEN’ to ‘LPS’[ LEN - 1].
- Make ‘i’ = 0 that will now point the character in ‘S’. Create another variable (say, ‘j’) that can point to a character in the word ‘X’. Set ‘j’ = 0.
- Create a vector ‘FOUND’ to store the starting index if, word ‘X’ is found in the ‘S’.
- Now, iterate till ‘i’ becomes greater than or equal to the length of ‘S’. (say, iterator = ‘i’)
- If the character corresponding to ‘i’ in ‘S’ is the same as the character corresponding to ‘j’ in the word ‘X’ then increment ‘i’ and ‘j’ by 1.
- If ‘j’ becomes equal to the length of the word ‘X’ then it means the complete word ‘X' found in ‘S’ and so, store (‘i’ - ‘j’) in vector ‘FOUND’. And, set ‘j’ to ‘LPS’[ j - 1].
- Else if, ‘i’ is less than the length of ‘S’ and X[ j ] is not equal to s[ i ].
- If, ‘j’ is 0 then simply increment ‘i’ by 1.
- Otherwise, set ‘j’ to ‘LPS’[ j - 1].
- Create a variable (say, ‘DECODE’) of string type to store the decoded string.
- Make a variable named ‘PREV’ to hold the previous index in ‘S’.
- Now, iterate through ‘FOUND’. (say, iterator = ‘K’)
- Check if, 'K’ is less than the ‘PREV’ then back to the previous step. This is done to handle cases where suppose, ‘X’ = “xx” and ‘S’ is containing “xxx” somewhere. By writing this condition we will only take the first two characters in this case.
- Append substring from “prev” to (‘K’ - ‘PREV’) in ‘DECODE’, as it will not contain any occurrence of the word ‘X’.
- Then there must be the word ‘X’ in the ‘S’ and so, append the word ‘R’ in ‘DECODE’.
- Now, set ‘PREV’ to ('K’ + X.size).
- After replacing all the occurrences of the word ‘X’ now, append the last remaining characters in the ‘DECODE’. Append substring from ‘PREV’ to (length of ‘S’ - ‘PREV’) in ‘DECODE’.
- Return the string ‘DECODE’.