給定一個字符串 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。您能指出是什么問題來解鎖我嗎？
1 回答
catspeake
TA貢獻1111條經驗 獲得超0個贊
問題是當您在刪除 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。
添加回答
舉報
0/150
提交
取消