Given two strings, the problem asks us to identify all occurrences of the smaller string and it's permutations in the larger string.
For example:
string_large="MISSISSIPPI"
string_small="IS"
Then the program must identify the following occurrences...{1,3,4,6}
Let's assume that the larger string is of length n and the smaller string is of length m.
A very brute force approach to solve this would be to generate all permutations of the smaller string and store them in a vector and then use strstr() to find all the occurrences. This would give a time complexity of O(m!) in the worst case(all the alpahabets in the string are different).
The approach suggested here is slightly better and does the job in O(m*n) time, using some extra space.
Approach:
The basic idea here is to maintain a hash which stores the number of occurences of each alphabet in the smaller string. Once this is done we start iterating in the larger string, maintaining a start index which tells us where the current string starts from.
For every start index in the large string, we call a new function which checks if the next m characters is a permutation of the smaller string. In this function, we run a loop of length m, and we check for every character if it has a non zero value in the hash.
If yes, we decrease this by 1 and move on.
If no, return false, as all the occurrences of that character has been exhausted, and a permutation is still not found.
Now, if the check function returns true, then we have found an occurrence and so we print this to the screen.
else repopulate the hash, and move the start index forward by 1.
Note:
1. Sometimes it is required to print -1 in case of no occurrence found, for this we can simply maintain a flag which can be set when the first occurrence is printed.
2. The below code works if the strings have lower case english alphabets. A larger hash can be maintained for a bigger character set.
For example:
string_large="MISSISSIPPI"
string_small="IS"
Then the program must identify the following occurrences...{1,3,4,6}
Let's assume that the larger string is of length n and the smaller string is of length m.
A very brute force approach to solve this would be to generate all permutations of the smaller string and store them in a vector and then use strstr() to find all the occurrences. This would give a time complexity of O(m!) in the worst case(all the alpahabets in the string are different).
The approach suggested here is slightly better and does the job in O(m*n) time, using some extra space.
Approach:
The basic idea here is to maintain a hash which stores the number of occurences of each alphabet in the smaller string. Once this is done we start iterating in the larger string, maintaining a start index which tells us where the current string starts from.
For every start index in the large string, we call a new function which checks if the next m characters is a permutation of the smaller string. In this function, we run a loop of length m, and we check for every character if it has a non zero value in the hash.
If yes, we decrease this by 1 and move on.
If no, return false, as all the occurrences of that character has been exhausted, and a permutation is still not found.
Now, if the check function returns true, then we have found an occurrence and so we print this to the screen.
else repopulate the hash, and move the start index forward by 1.
Note:
1. Sometimes it is required to print -1 in case of no occurrence found, for this we can simply maintain a flag which can be set when the first occurrence is printed.
2. The below code works if the strings have lower case english alphabets. A larger hash can be maintained for a bigger character set.
Read full article from Find all occurrences of all permutations of a smaller string in a larger string. | CODING INTERVIEW ARCHIVES
No comments:
Post a Comment