fork download
copy 
  1.  
  2. import java.util.HashMap;
  3. import java.util.Map;
  4.  
  5. /**
  6.  * Minimum Window in which all the words are found
  7.  * @author PRATEEK
  8.  */
  9.  class MinWindowContainingAllWords {
  10.  
  11. 	private static int minWindow = 9999; // length of minimum window
  12. 	private static int startWord = 0; // start position
  13. 	private static int endWord = 0; // end position
  14.  
  15. 	/**
  16. 	 * Sub-routine to minumum window in which all words of pattern are found in
  17. 	 * the given string
  18. 	 * 
  19. 	 * @param str
  20. 	 *            : input String
  21. 	 * @param pat
  22. 	 *            : pattern
  23. 	 */
  24. 	public static void minWindow(String str, String pat) {
  25.  
  26. 		Map<String, Integer> toFind = new HashMap<String, Integer>(); // words
  27. 																		// to be
  28. 																		// found
  29. 		Map<String, Integer> found = new HashMap<String, Integer>(); // the set
  30. 																		// of
  31. 																		// words
  32. 																		// which
  33. 																		// are
  34. 																		// found
  35.  
  36. 		int foundCount = 0;
  37. 		// left pointer of the window, which is moved when all required wrds are
  38. 		// found,
  39. 		// and is moved until any word from required word is found
  40. 		int tempStart = 0;
  41.  
  42. 		// Tokenising Text
  43. 		String[] words = str.split(" ");
  44. 		int sLen = words.length;
  45.  
  46. 		// Tokenising Pattern
  47. 		String[] patTokens = pat.split(" ");
  48. 		int pLen = patTokens.length;
  49.  
  50. 		// filling the 'toFind' map
  51. 		for (String val : patTokens)
  52. 			toFind.put(val, toFind.get(val) == null ? 1 : toFind.get(val) + 1);
  53.  
  54. 		// traversing over text length
  55. 		for (int index = 0; index < sLen; index++) {
  56. 			String word = words[index];
  57.  
  58. 			if (!toFind.containsKey(word))
  59. 				continue;
  60.  
  61. 			found.put(word, found.get(word) == null ? 1 : found.get(word) + 1);
  62.  
  63. 			if (toFind.get(word) >= found.get(word))
  64. 				foundCount++;
  65.  
  66. 			if (foundCount == pLen) {
  67. 				// reduce window size until conditions are violated
  68. 				word = words[tempStart];
  69. 				while (!toFind.containsKey(word)
  70. 						|| toFind.get(word) < found.get(word)) {
  71. 					// Discard excess count of the given word
  72. 					if (toFind.containsKey(word))
  73. 						found.put(word, found.get(word) - 1);
  74.  
  75. 					// get next word, to check if it can be discarded
  76. 					word = words[++tempStart];
  77. 				}
  78.  
  79. 				// Updating Min Window
  80. 				if (minWindow > index - tempStart + 1) {
  81. 					minWindow = index - tempStart + 1;
  82. 					startWord = tempStart;
  83. 					endWord = index;
  84. 				}
  85. 			}
  86. 		}
  87. 	}
  88.  
  89. 	public static void main(String[] args) {
  90.  
  91. 		String str = "Shopping with xyz.com is an awesome experience";
  92. 		String pat = "awesome with xyz.com";
  93. 		minWindow(str, pat);
  94. 		//System.out.println("Start :" + startWord + "   End : " + endWord);
  95.  
  96. 		System.out.println("Window Containing all words");
  97. 		// Tokenising Text
  98. 		String[] words = str.split(" ");
  99. 		for(int i=startWord;i<=endWord;i++)
  100. 		{
  101. 			System.err.print(words[i]+"  ");
  102. 		}
  103.  
  104. 	}
  105. }
  106.  
Success #stdin #stdout #stderr 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Window Containing all words
stderr
copy 
with  xyz.com  is  an  awesome
https://ideone.com/eExVsz
Minimum Window containing all words
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!