java - find Minimum window substring - leetcode - 解决方案不工作

Question

问题:https://leetcode.com/problems/minimum-window-substring/

给定一个字符串 S 和一个字符串 T，找到 S 中包含 T 中所有字符的最小窗口，复杂度为 O(n)。

例子:

输入:S = "ADOBECODEBANC", T = "ABC"输出:“BANC”

我努力尝试使用滑动窗口技术提出解​​决方案，但我被困在这里。有人可以帮忙吗？

    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

When you are doing that, unknowingly your code did not take B (at index 9) into account and end pointer reached A (at index 10).

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

ADOBECODEBANC
    ^     ^
  begin  end

因此您得到的答案是ADOBEC

What you could do to correct that when end pointer finds any character which must be accounted, remove the first index of that character and add the one encountered recently.

Once that done you could easily ignore that character when begin pointer encounters it as the frequency of that character wouldn't affect.

This is valid since we want to shrink window from the beginning, not from the end.

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

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

此外，您应该从头到尾打印值。
s.substring(开始, 结束)

考虑 begin = 8 和 end = 10 的情况
s.substring(8, 10)，不是 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;
}

突出显示我更改的部分。

Note: This code solves only your use case and is NOT supposed to give AC on all test-cases.