สมมติว่าเรามีสตริง S และ T เราต้องหาหน้าต่างขั้นต่ำใน S ซึ่งจะมีอักขระทั้งหมดใน T ดังนั้นหากอินพุตเป็นเหมือน “ABHDAXCVBAGTXATYCB” และ T =“ABC” ผลลัพธ์จะเป็น:“ CVBA”.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สร้างหนึ่งแผนที่ m
-
เก็บความถี่ของ x เป็น m
-
length :=ขนาดของ s, left :=0, right :=0, ansLeft :=0 and ansRight :=0
-
ตัวนับ :=ขนาดของ x, แฟล็ก :=false, ans :=สตริงว่าง
-
ในขณะที่ส่วนสูง <ขนาดของ s −
-
ค :=s[ขวา]
-
ถ้า c มีอยู่ใน m แล้ว
-
ถ้า m[c]> 0 ให้ลดตัวนับลง 1
-
ลด m[c] ลง 1
-
-
ในขณะที่เคาน์เตอร์ =0 และซ้าย <=ขวา
-
ถ้าขวา – ซ้าย + 1 <=ความยาว
-
ความยาว :=ขวา – ซ้าย + 1
-
ธง :=จริง
-
ansLeft :=ซ้าย ansRight :=ขวา
-
-
ถ้าซ้าย =ขวา ให้ตัดวงจร
-
c :=s[ซ้าย]
-
ถ้า c มีอยู่ใน m ให้เพิ่ม m[c] ขึ้น 1
-
ถ้า m[c]> 0 ให้เพิ่มตัวนับขึ้น 1
-
เพิ่มขึ้น 1
-
-
เพิ่มสิทธิ์ 1
-
-
ถ้าแฟล็กเป็นเท็จ ให้คืนค่า ans
-
มิฉะนั้นสำหรับฉันในช่วง ansLeft ถึง ansRight ให้เพิ่ม ans โดย s[i]
-
กลับมาอีกครั้ง
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h> using namespace std; class Solution { public: string minWindow(string s, string x) { map <char, int> m; for(int i =0;i<x.size();i++)m[x[i]]++; int length = s.size(); int left = 0, right = 0 , ansLeft = 0, ansRight = 0; int counter = x.size(); bool flag = false; string ans = ""; while(right<s.size()){ char c = s[right]; if(m.find(c)!=m.end()){ if(m[c]>0)counter--; m[c]--; } while(counter == 0 && left<=right){ if(right-left+1 <=length){ length = right-left+1; flag = true; ansLeft = left; ansRight = right; } if(left == right)break; c = s[left]; if(m.find(c)!=m.end()){ m[c]++; if(m[c]>0)counter++; } left++; } right++; } if(!flag)return ans; else for(int i =ansLeft;i<=ansRight;i++)ans+=s[i]; return ans; } }; main(){ Solution ob; cout << (ob.minWindow("ABHDAXCVBAGTXATYCB", "ABC")); }
อินพุต
"ABHDAXCVBAGTXATYCB" "ABC"
ผลลัพธ์
CVBA