找到最小窗口子字符串 - leetcode - 解决方案不起作用

Question

给定一个字符串 S 和一个字符串 T，找到 S 中包含 T 中所有字符的最小窗口，复杂度为 O(n)。例子：输入：S =&ldquo;ADOBECODEBANC&rdquo;，T =&ldquo;ABC&rdquo;输出：&ldquo;BANC&rdquo;我努力尝试使用滑动窗口技术提出解决方案，但我被困在这里。有人可以帮忙吗？    package com.tryPrep.Strings;import java.util.HashMap;public class MinWindowSubstring {    static String minWinSubStr(String s, String t){        HashMap<Character, Integer> tabl = new HashMap<>();        for(char c: t.toCharArray()){            int charCount=0;            if(tabl.containsKey(c))              charCount = tabl.get(c);            tabl.put(c, charCount+1);        }        int begin =0, end =0, counter=tabl.size();        String ans="";        int max=s.length();        while(end < s.length()) {            char endChar = s.charAt(end);            if (tabl.containsKey(endChar)) {                int charCount = tabl.get(endChar);                if (charCount > 0) {                    counter--;                    tabl.put(endChar, charCount - 1);                }            }            end++;            while (counter == 0) {                if (max > end - begin) {                    ans = s.substring(begin, end - begin);                    max = ans.length();                }                char beginChar = s.charAt(begin);                if (tabl.containsKey(beginChar)) {                    int charCount = tabl.get(beginChar);                    if(charCount == 0) {                        tabl.put(beginChar, charCount + 1);                        counter++;                    }                }                begin++;            }        }        return ans;    }    public static void main(String[] args) {        String s = "ADOBECODEBANC";        String t = "ABC";        System.out.println("minWinSubStr M1 : " + minWinSubStr(s, t));    }}输出 ：minWinSubStr M1 : ADOBEC我看到当 end 达到字符串长度时循环得到满足，但计数器仍然不为 0。您能指出是什么问题来解锁我吗？

Answer 1

问题是当您在删除 A（索引 0 处）后增加计数器时。你开始寻找另一个A来弥补这一损失。

ADOBECODEBANC

 ^        ^

begin    end

当您这样做时，您的代码不知不觉地没有考虑 B（在索引 9 处），并且结束指针到达了 A（在索引 10 处）。

之后，当开始指针到达 B （索引 4 处）并且您递增计数器时，您的结束指针无法找到任何其他 B。

ADOBECODEBANC

    ^     ^

  begin  end

因此你得到的答案是ADOBEC

当结束指针找到必须考虑的任何字符时，您可以做些什么来纠正，删除该字符的第一个索引并添加最近遇到的索引。

一旦完成，当开始指针遇到该字符时，您可以轻松忽略该字符，因为该字符的频率不会影响。

这是有效的，因为我们想要从开始而不是从末尾缩小窗口。

在您的情况下，每次结束指针遇到tabl中的任何字符时，您都可以减少计数器。

现在，当开始指针遇到任何值为负的字符时，不要增加计数器，只需将值加一即可。

另外，您应该从头到尾打印值。

s.substring(begin, end)

考虑当 begin = 8 和 end = 10 时的情况

s.substring(8, 10), not s.substring(8, 2)

static String minWinSubStr(String s, String t) {

    System.out.println(s);

    System.out.println(t);

    HashMap<Character, Integer> tabl = new HashMap<>();

    for (char c : t.toCharArray()) {

        int charCount = 0;

        if (tabl.containsKey(c))

            charCount = tabl.get(c);

        tabl.put(c, charCount + 1);

    }

    int begin = 0, end = 0, counter = tabl.size();

    String ans = "";

    int max = s.length();

    while (end < s.length()) {

        char endChar = s.charAt(end);

        if (tabl.containsKey(endChar)) {

            int charCount = tabl.get(endChar);

            if (charCount > 0) {

                counter--;

            }

            tabl.put(endChar, charCount - 1);

        }

        end++;

        while (counter == 0) {

            if (max > end - begin) {

                ans = s.substring(begin, end);

                max = ans.length();

            }

            char beginChar = s.charAt(begin);

            if (tabl.containsKey(beginChar)) {

                int charCount = tabl.get(beginChar);

                if(charCount < 0) {

                    tabl.put(beginChar, charCount + 1);

                }

                else if (charCount == 0) {

                    tabl.put(beginChar, charCount + 1);

                    counter++;

                }

            }

            begin++;

        }

    }

    return ans;

}

突出显示我更改的部分。

注意：此代码仅解决您的用例，不应在所有测试用例上提供 AC。