Databases
StackOverflow2013
Postsdbo
POmethod to find the shortest substring containing the given words:optimization required
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POmethod to find the shortest substring containing the given words:optimization required
    text
    copied!<p>I have a program that requires me to find the shortest subsegment of a given String, containing a list of words. Even though my program is correct, I am failing to deliver within a time frame of execution(5 seconds). I figured the problem is because of the complex(trivial) algorithm I am using. It consists of nested loops, and requires multiple scan of the list_of_words array.Here is my code for the search function. <code>a[]</code> contains the original string,stored by words, <code>b[]</code> contains the list of the words which is to be found to form the subsegment. <code>String g</code>stores the temporary subsegment formed by words from original string including the words in the list. </p> <pre><code>private static void search() // Function to find the subsegment with a required list of words { int tail,x;//counters String c[]=new String[b.length]; //initializing a temporary array to copy the list of words array. for(int i =0; i&lt;a.length;i++)// looping throw original string array { System.arraycopy(b, 0, c, 0, b.length);//copying the list of words array to the temporary array for (int j=0;j&lt;b.length;j++)//looping throw the temporary array { x=0; //counter for temporary array if(a[i].equalsIgnoreCase(b[j]))//checking for a match with list of words { tail=i; //adds the words starting from the position of the first found word(tail) till all the words from the list are found while((x&lt;b.length)&amp;&amp;(tail&lt;a.length)) { g=g+" "+a[tail];//adds the words in the string g for(int k=0;k&lt;c.length;k++) //checks for the found word from the temporary array and replaces it with "" { if(c[k].equalsIgnoreCase(a[tail])) { c[k]=""; x++; } } tail++; } if((tail==a.length)&amp;&amp;(x!=b.length))//checks if the string g does not contains all the listed word { g=""; } else { count(g);g="";//check for the shortest string. } } } }print(); } </code></pre> <p>Sample : </p> <p>Original String :This is a test. This is a programming test. a programming test this is. </p> <p>Words to be found : this , test, a ,programming. </p> <p>Subsegments :</p> <p>This is a test This is a programming </p> <p>This is a programming test </p> <p>a programming test a programming test this</p> <p>programming test a programming test this</p> <p>test a programming test this</p> <p>a programming test this </p> <p>Shortest Sub segment : a programming test this</p> <p>Any suggestion regarding change in the data structures or looping structures or even changes in the algorithm that optimizes the same will be helpful.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload