c# - 我的算法中查找包含精确字符集的最小子字符串的大小的缺陷在哪里？

Question

设置是我有一个像

这样的字符串

s = "GAAATAAA" 

和像

这样的字典

surpdic = { 'A' -> 4 }

字典的意思是s有4个多余的A个字符。

我的算法试图找到的是包含 4 A 的 s 的最小子串的大小。我不明白为什么它不能处理所有的测试用例。

它应该像这样工作

GAAATAAA
 ||| |||
 i|| j||  j - i = 4, mindiff = 4
  ||  ||
  i|  j|  j - i = 4, mindiff = 4
   |   | 
   i   j  j - i = 4, mindiff = 4

在我提供的示例中。换句话说，在字符串中从左到右，找到第一个包含所有字符的span，然后有效地取出左指针并将其移动到下一个可能的span的开头；一直跟踪最小跨度。

int mindiff = Int32.MaxValue; 
int left = 0; 
while(!surpdic.ContainsKey(s[left++]));
for(int right = left; right < s.Length; ++right) 
{                   
    if(surpdic.ContainsKey(s[right])) 
        surpdic[s[right]] -= 1; 
    if(surpdic.Values.All(count => count == 0)) 
    {
        int diff = right - left; 
        if(diff < mindiff) 
            mindiff = diff;

        surpdic[s[left]] += 1; 
        while(!surpdic.ContainsKey(s[left++])); 
    }
}

编辑:所以这是一个给我运行时错误的案例。

using System.IO;
using System.Linq;
using System.Text;
using System;
using System.Collections.Generic;
public class Solution
{   

    static int SmallestSubstringContainingChars(string source, Dictionary<char,int> surpdic)
    {
        int mindiff = Int32.MaxValue; 
        int left = 0; 
        while(!surpdic.ContainsKey(source[left++]));
        for(int right = left; right < source.Length; ++right) 
        {                   
            if(surpdic.ContainsKey(source[right])) 
                surpdic[source[right]] -= 1; 
            if(surpdic.Values.All(count => count == 0)) 
            {
                int diff = right - left; 
                if(diff < mindiff) 
                    mindiff = diff;

                surpdic[source[left]] += 1; 
                while(!surpdic.ContainsKey(source[left++])); 
            }
        }
        return mindiff + 1;
    }

    public void Main(string[] args)
    {
        string s = "ACTGATTT";
        Dictionary<char,int> d = new Dictionary<char,int>() { { 'A' , 1 }, { 'T' , 3 } };
        Console.WriteLine( SmallestSubstringContainingChars(s,d));
    }
}

Answer 1

我在你的代码中发现了很多问题。

首先是你向左递增的方式。

此外，您正在修改字典，因此下一次执行将从错误的字典开始，这就是我创建副本的原因。

如果字典条目的值已经为 0，则不要递减它，否则您的 All 代码将不起作用。

检查下面的代码，如果您有什么不明白的地方，请在下面评论。如果未找到所需的模式，它将返回 -1:

static int SmallestSubstringContainingChars(string source, Dictionary<char, int> surpdic)
{
    int mindiff = -2;

    int left = 0;
    while (left<source.Length)
    {
        if (surpdic.ContainsKey(source[left]))
        {
            Dictionary<char, int> md = new Dictionary<char, int>(surpdic);
            md[source[left]] -= 1;
            for (int right = left; right < source.Length; ++right)
            {
                if (md.ContainsKey(source[right]) && md[source[right]]>0)
                    md[source[right]] -= 1;
                if (md.Values.All(count => count == 0))
                {
                    int diff = right - left;
                    if (mindiff==-2 || diff < mindiff)
                        mindiff = diff;
                }
            }
        }
        left++;
    }
    return mindiff + 1;
}