java - 查找包含给定单词 :optimization required 的最短子字符串的方法

Question

我有一个程序要求我找到给定字符串的最短子段，其中包含一个单词列表。即使我的程序是正确的，我也未能在执行时间范围内(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

动态规划解决方案:

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

拥有您正在寻找的不同可见单词的总数(永远不会减少，最大值 = 您正在寻找的单词数)。

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

• 如果该词存在于您要查找的词列表中，则更新该词的最后位置。
• 如果未初始化更新的最后位置，则增加总计数。
• 如果总计数等于最大值，则遍历最后一个位置并找到最小的一个。当前位置和该值之间的距离将是子字符串的长度。记录这些值并找出所有位置中最好的一个。

一个优化是拥有a heap对于最后位置以减少找到最小位置所花费的时间(应该与一些结构(可能是散列图或 TreeMap )一起使用，允许在给定单词的情况下快速查找堆中的指针)。

示例:

输入:这是一个测试。这是一个编程测试。这是一个编程测试

寻找: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

最佳结果:对此进行编程测试，长度 = 4。

复杂性分析:

令 n 为输入中的单词数，k 为我们要查找的单词数。

该算法只通过一次输入，并且在每一步中，O(log k) 为 getMin 操作(使用堆优化)工作。

因此花费的总时间是O(n log k)。

处理重复项:

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