找到包含给定单词的最短子串的方法:需要优化

Question

我有一个程序,要求我找到给定String的最短子段,包含一个单词列表.即使我的程序是正确的,我也无法在执行的时间范围内(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();
}

样品:

原始字符串:这是一个测试.这是一个编程测试.这是一个编程测试.

可以找到的词:this,test,a,programming.

子分段:

这是一个测试这是一个编程

这是一个编程测试

编程测试一个编程测试

编程测试这个编程测试

测试一个编程测试

编程测试这个

最短子段:编程测试

关于数据结构或循环结构的变化的任何建议,或甚至优化相同的算法的变化都将是有帮助的.

Answer 1

动态编程解决方案

为您要查找的每个单词设置最后一个位置变量.

拥有您正在寻找的截然不同的单词的总数(永远不会减少,max =您正在寻找的单词数).

对于输入中的每个单词位置:

• 如果您要查找的单词列表中存在该单词,请更新该单词的最后位置.
• 如果未初始化更新的最后位置,则增加总计数.
• 如果总计数等于最大值,则循环通过最后位置并找到最小位置.当前位置与该值之间的距离将是子字符串的长度.记录这些值并找到所有位置的最佳值.

优化是为最后一个位置设置一个堆,以减少找到最小位置所需的时间(应该与一些结构(可能是散列或树映射)一起使用,允许快速查找指向一个字的堆中的指针).

例:

输入: This is a test. This is a programming test. a programming test this is

寻找: this, test, a, programming

                1    2  3  4     5    6  7  8           9     10 11          12   13   14
                This is a  test. This is a  programming test. a  programming test this is
this         -1 1    1  1  1     5    5  5  5           5     5  5           5    13   13
test         -1 -1   -1 -1 4     4    4  4  4           9     9  9           12   12   12
a            -1 -1   -1 3  3     3    3  7  7           7     10 10          10   10   10
programming  -1 -1   -1 -1 -1    -1   -1 -1 8           8     8  11          11   11   11
Count        0  1    1  2  3     3    3  3  4           4     4  4           4    4    4
Substr len   NA NA   NA NA NA    NA   NA NA 5           5     6  7           8    4    5
Shortest len NA NA   NA NA NA    NA   NA NA 5           5     5  5           5    4    4

最佳结果:a programming test this,长度= 4.

复杂性分析:

让我们n在输入单词的数量,k我们正在寻找的单词数.

该算法只传递一个输入,并且在每个步骤中都O(log k)可以进行getMin操作(使用堆优化).

因此,所花费的总时间是O(n log k).

处理重复:

如果我们正在寻找的单词中允许重复(并且目标序列必须匹配所有出现),上面的算法将不会按原样运行,但一个简单的解决方法是让每个不同的单词都有自己的指针堆原始堆(此堆中的值与原始堆中的值相同),此堆的最大大小是我们要查找的单词中该单词的出现次数.