Problem Statement:
Find the minimum window in which all the words of the pattern string are present in the input string.
Text "Shopping with xyz.com is an awesome experience"
Pattern : "awesome with xyz.com"
Output : "with xyz.com is an awesome"
The output window contains all words of pattern in text.
Download Source Code
Solution:
The approach to solve the problem is to have two pointers of the window , as left and right.
The right pointer is moved to the right until all words in the text are found, once all the required words are found the left pointer is moved to its right to discard the words on the left hand of the window.
The approach used is based on Sliding Window. In this approach we take pointers at extreme left and extreme right. The right pointer is moved to its right in search of required words, once the window contains all required words, the left pointer tries to decrease size of the window with all the required words.
If the current window length is smaller smaller than previous one , it is recorded or updated.
Complexity: O(n) + O(n) = O(n)
Below is the implementation
Please comment and post your suggestions.
Happy Coding !! :)
Find the minimum window in which all the words of the pattern string are present in the input string.
Text "Shopping with xyz.com is an awesome experience"
Pattern : "awesome with xyz.com"
Output : "with xyz.com is an awesome"
The output window contains all words of pattern in text.
Download Source Code
Solution:
The approach to solve the problem is to have two pointers of the window , as left and right.
The right pointer is moved to the right until all words in the text are found, once all the required words are found the left pointer is moved to its right to discard the words on the left hand of the window.
The approach used is based on Sliding Window. In this approach we take pointers at extreme left and extreme right. The right pointer is moved to its right in search of required words, once the window contains all required words, the left pointer tries to decrease size of the window with all the required words.
If the current window length is smaller smaller than previous one , it is recorded or updated.
Complexity: O(n) + O(n) = O(n)
Below is the implementation
private static int minWindow = 9999; // length of minimum window private static int startWord = 0; // start position private static int endWord = 0; // end position /** * Sub-routine to minumum window in which all words of pattern are found in * the given string * @param str : input String * @param pat : pattern */ public static void minWindow(String str, String pat) { // words to be found MaptoFind = new HashMap (); // the set of words which are found Map found = new HashMap (); int foundCount = 0; // left pointer of the window, which is moved when all required wrds are // found, // and is moved until any word from required word is found int tempStart = 0; // Tokenising Text String[] words = str.split(" "); int sLen = words.length; // Tokenising Pattern String[] patTokens = pat.split(" "); int pLen = patTokens.length; // filling the 'toFind' map for (String val : patTokens) toFind.put(val, toFind.get(val) == null ? 1 : toFind.get(val) + 1); // traversing over text length for (int index = 0; index < sLen; index++) { String word = words[index]; if (!toFind.containsKey(word)) continue; found.put(word, found.get(word) == null ? 1 : found.get(word) + 1); if (toFind.get(word) >= found.get(word)) foundCount++; if (foundCount == pLen) { // reduce window size until conditions are violated word = words[tempStart]; while (!toFind.containsKey(word) || toFind.get(word) < found.get(word)) { // Discard excess count of the given word if (toFind.containsKey(word)) found.put(word, found.get(word) - 1); // get next word, to check if it can be discarded word = words[++tempStart]; } // Updating Min Window if (minWindow > index - tempStart + 1) { minWindow = index - tempStart + 1; startWord = tempStart; endWord = index; } } } }
Please comment and post your suggestions.
Happy Coding !! :)
No comments:
Post a Comment