単語のリストを含む、特定の文字列の最短のサブセグメントを見つける必要があるプログラムがあります。私のプログラムは正しいのですが、実行時間枠 (5 秒) 内に配信できません。問題は、使用している複雑な（自明な）アルゴリズムが原因であると考えました。ネストされたループで構成され、list_of_words 配列の複数回のスキャンが必要です。検索関数のコードは次のとおりです。a[]単語ごとに格納された元の文字列をb[]含み、サブセグメントを形成するために検出される単語のリストを含みます。String gリスト内の単語を含む元の文字列からの単語によって形成された一時的なサブセグメントを格納します。
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<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<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<b.length)&&(tail<a.length))
{
g=g+" "+a[tail];//adds the words in the string g
for(int k=0;k<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)&&(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();
}
サンプル ：
元の文字列 :これはテストです。これはプログラミングのテストです。これはプログラミングテストです。
見つけられる言葉：これ、テスト、プログラミング。
サブセグメント :
これはテストです これはプログラミングです
プログラミングのテストです
プログラミングテスト プログラミングテスト これ
プログラミング テスト プログラミング テスト これ
プログラミングをテストする これをテストする
プログラミングテストこれ
最短サブ セグメント: プログラミング テストこれ
データ構造またはループ構造の変更、さらにはそれらを最適化するアルゴリズムの変更に関する提案は役に立ちます。