查找包含另一个字符串中字符串的所有字符的最小窗口的长度

Question

最近我接受了采访.我做得不好因为我遇到了以下问题

假设给出了一个序列:ADCBDABCDACD和搜索序列如下:ACD

任务是在给定字符串中查找包含保留顺序的搜索字符串的所有字符的开始和结束索引.

输出:假设索引从1开始:

开始指数10结束指数12

解释:

1.start/end index分别不是1/3,因为虽然它们包含字符串但是没有维护顺序

2.start/end index分别不是1/5,因为它们虽然包含顺序的字符串,但长度不是最佳的

3.start/end index分别不是6/9,因为它们虽然包含顺序中的字符串但长度不是最佳的

请查看如何查找包含给定字符串中所有字符的最小子字符串？.

但上述问题不同,因为订单未得到维护.我仍在努力维持索引.任何帮助,将不胜感激 .谢谢

Answer 1

我使用单个队列修改了之前的建议，现在我相信该算法随O(N*m)时间运行：

FindSequence(char[] sequenceList)
{
    queue startSeqQueue;
    int i = 0, k;
    int minSequenceLength = sequenceList.length + 1;
    int startIdx = -1, endIdx = -1;

    for (i = 0; i < sequenceList.length - 2; i++)
    {
        if (sequenceList[i] == 'A')
        {
            startSeqQueue.queue(i);
        }
    }

    while (startSeqQueue!=null)
    {
        i = startSeqQueue.enqueue();
        k = i + 1;

        while (sequenceList.length < k && sequenceList[k] != 'C')
            if (sequenceList[i] == 'A') i = startSeqQueue.enqueue();
            k++;

        while (sequenceList.length < k && sequenceList[k] != 'D')
            k++;

        if (k < sequenceList.length && k > minSequenceLength > k - i + 1)
        {
            startIdx = i;
            endIdx = j;
            minSequenceLength = k - i + 1;
        }
    }

    return startIdx & endIdx
}

我之前的（O(1) 内存）建议：

FindSequence(char[] sequenceList)
{
    int i = 0, k;
    int minSequenceLength = sequenceList.length + 1;
    int startIdx = -1, endIdx = -1;

    for (i = 0; i < sequenceList.length - 2; i++)
        if (sequenceList[i] == 'A')
            k = i+1;
            while (sequenceList.length < k && sequenceList[k] != 'C')
                k++;
            while (sequenceList.length < k && sequenceList[k] != 'D')
                k++;

            if (k < sequenceList.length && k > minSequenceLength > k - i + 1)
            {
                startIdx = i;
                endIdx = j;
                minSequenceLength = k - i + 1;
            }

    return startIdx & endIdx;
}