找到最小窗口长度包含字符串的所有字符在另一个字符串 [英] Find length of smallest window that contains all the characters of a string in another string

问题描述

最近我一直在接受采访。我没有做好的原因我被困在以下问题

Recently i have been interviewed. I didn't do well cause i got stuck at the following question

假设一个序列提供：ADCBDABCDACD 和搜索顺序是这样的：A C D

suppose a sequence is given : A D C B D A B C D A C D and search sequence is like: A C D

任务是找到一个包含搜索字符串$ P $的所有pserving顺序字符的起始和给定字符串中结束索引。

task was to find the start and end index in given string that contains all the characters of search string preserving the order.

输出：假设指数从1开始：

Output: assuming index start from 1:

开始索引10 结束索引12

start index 10 end index 12

解释

1.开始/结束索引都没有分别的1/3，因为尽管它们所包含的字符串，但为了不保持

1.start/end index are not 1/3 respectively because though they contain the string but order was not maintained

2.启动/结束索引都没有分别为1/5，因为虽然它们包含字符串的顺序，但长度不是最佳的。

2.start/end index are not 1/5 respectively because though they contain the string in the order but the length is not optimum

3.启动/结束索引都没有分别为6/9，因为虽然它们包含字符串的顺序，但长度不是最佳的。

3.start/end index are not 6/9 respectively because though they contain the string in the order but the length is not optimum

请通过<一个href="http://stackoverflow.com/questions/2459653/how-to-find-smallest-substring-which-contains-all-characters-from-a-given-string">How发现其中包含给定字符串中的所有字符最小的子？。

但上面的问题是不同的，因为顺序不会被维持。我仍然在努力维持指标。任何帮助将是AP preciated。谢谢

But the above question is different since the order is not maintained. I'm still struggling to maintain the indexes. Any help would be appreciated . thanks

推荐答案

我试着写一些简单的C code来解决问题：

I tried to write some simple c code to solve the problem:

更新：

我写了搜索函数，它会在正确的顺序所需要的字符，返回窗口的长度和存储窗起点 INT * startAt 。该函数处理的干草的子序列从指定的起始点 INT启动来它的结束

I wrote a search function that looks for the required characters in correct order, returning the length of the window and storing the window start point to ìnt * startAt. The function processes a sub-sequence of given hay from specified startpoint int start to it's end

该算法的其余部分位于主其中，所有可能的子序列进行测试用小的优化：我们开始$的起始点后立即寻找下一个窗口p $ pvious之一，所以我们跳过一些不必要的转弯。在这个过程中，我们跟踪f显示，直到，现在最好的解决办法

The rest of the algorithm is located in main where all possible subsequences are tested with a small optimisation: we start looking for the next window right after the startpoint of the previous one, so we skip some unnecessary turns. During the process we keep track f the 'till-now best solution

复杂度为O（N * N / 2）

Complexity is O(n*n/2)

UPDATE2：

不必要的依赖已被删除，不需要后续调用的strlen（...）已被替换传递给搜索（尺寸参数.. 。）

unnecessary dependencies have been removed, unnecessary subsequent calls to strlen(...) have been replaced by size parameters passed to search(...)

#include <stdio.h>

// search for single occurrence
int search(const char hay[], int haySize, const char needle[], int needleSize, int start, int * startAt)
{
    int i, charFound = 0;

    // search from start to end
    for (i = start; i < haySize; i++)
    {
        // found a character ?
        if (hay[i] == needle[charFound])
        {               
            // is it the first one?
            if (charFound == 0) 
                *startAt = i;   // store starting position
            charFound++;    // and go to next one
        }
        // are we done?
        if (charFound == needleSize)
            return i - *startAt + 1;    // success
    }
    return -1;  // failure
}

int main(int argc, char **argv)
{

    char hay[] = "ADCBDABCDACD";
    char needle[] = "ACD";

    int resultStartAt, resultLength = -1, i, haySize = sizeof(hay) - 1, needleSize = sizeof(needle) - 1;

    // search all possible occurrences
    for (i = 0; i < haySize - needleSize; i++)
    {
        int startAt, length;

        length = search(hay, haySize, needle, needleSize, i, &startAt);

        // found something?
        if (length != -1)
        {
            // check if it's the first result, or a one better than before
            if ((resultLength == -1) || (resultLength > length))
            {
                resultLength = length;
                resultStartAt = startAt;
            }
            // skip unnecessary steps in the next turn
            i = startAt;
        }
    }

    printf("start at: %d, length: %d\n", resultStartAt, resultLength);

    return 0;
}

这篇关于找到最小窗口长度包含字符串的所有字符在另一个字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！