在我的算法中找到包含精确字符集的最小子字符串的大小的缺陷在哪里

本文关键字：在哪里 缺陷 字符串 字符集 算法 我的 包含精 | 更新日期: 2023-09-27 18:02:15

设置是我有一个像

这样的字符串
s = "GAAATAAA"

和像

这样的字典
surpdic = { 'A' -> 4 }

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

我的算法寻求的是包含4 A s的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++])); 
    }
}

Edit:所以这是一个给我一个运行时错误的情况。

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));
    }
}

在我的算法中找到包含精确字符集的最小子字符串的大小的缺陷在哪里

我发现你的代码有很多问题。

首先是向左递增的方式。

而且，你正在修改字典，所以下一次执行将从一个错误的字典开始，这就是为什么我要创建一个副本。

如果字典条目的值已经是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;
}
相关文章：