Twitter 🤥
Hello everyone, I’m Pan Xiao ‘an! A forever on the road to weight loss front er🐷!
On March 19, 2022, Beijing time, I found a draft of the idea that I deliberately practiced in the sliding window created on July 19, 2021. I picked it up and wrote with the help of this New Year flag and the recent training camp brush problem plan.
I happened to read a book that said, I am not afraid that your plan is not completed on time, but that you are immersed in remorse and self-denial because the plan is not completed, and then there will be no new plan. I used to be so upset that I didn’t realize my flag, but I gradually got over it. Accept that you have written a plan that doesn’t work as planned, and move forward little by little, on the way is good.
Serving 🥬
Straight to the point:
I give you a string S, a string t. Returns the smallest string in S that covers all characters of t. Return an empty string “” if there is no substring in S that covers all characters of t.
Input: s = "ADOBECODEBANC", t = "ABC" output: "BANC"Copy the codeInput: s = "a", t = "a" output: "a"Copy the codeInput: s = "a", t = "aa" Output: "" Explanation: both characters 'a' in t should be included in the substring of S, so there is no qualified substring, return empty string.Copy the codeWatch its color smell its taste 🐽
Read the topic to write code, in the algorithm of the trap. When we get the topic, the first time is to “observe its color and smell its taste”. In other words, it is necessary to clear up the logic and see what part of the knowledge point this question is to investigate. We want to find the shortest substring that contains the t target string. To break it down, we want to solve two problems:
- How do I identify inclusion
- How to determine the shortest
And then we’re going to look for a solution to this problem from these two subproblems.
How do I identify substrings that contain target strings?
If you are given two strings s and t, you are asked to determine whether S contains t. What would you think? My first idea was to iterate over all the characters in T, save them in an object tmap, and count them.
var generateMap = function (t) {
let tmap = {}
for (let key of t) {
if(tmap[key] ! =undefined) {
tmap[key]++
} else {
tmap[key] = 1}}return tmap
}
Copy the codeAfter that, the substring S is traversed. If characters are found in Tmap, the number of characters is reduced by 1. When all values in the object are less than or equal to 0, it means that S completely contains T.
var iscontained = function (tmap) {
let values = Object.values(tmap)
return values.filter(item= > item <= 0).length == values.length
}
Copy the codeWriting here, I seem to have solved the problem for the time being. But when do we call this method to make a judgment? Every time you hit it? This is obviously not efficient and wastes many invalid judgments.
Is there a better, easier way to tell? The answer is yes! We introduce a new variable typenum to represent the types of all letters in tmap:
let typenum=Object.keys(tmap).length
Copy the codeWhen traversing s, in addition to subtracting the tmap value by 1 after each hit, we can also determine whether the value is 0 or not. If it is 0, then we can subtract typenum by 1.
For example, if s is “ACBBCD” and t is “ABB”, we use t to create the following object. Typenum is 2:
{
A:1.B:2
}
Copy the codeWhen we iterate from s to “A”, “A” in the object is 0, which means that S has overwritten “A” in t. At this point, we also reduce typenum by 1. When we iterate to the last B, typenum is zero, and the substring is “ACBB”. The conclusion is that we use a variable typenum combined with TMAP to determine whether the substring is covered or not, instead of using iscontained. The advantage is that after the introduction of typenum variable, the problem of timing judgment and method judgment is solved.
How to determine the shortest
Let’s use the first example of this problem to help us understand the logic and thinking process of sliding Windows. If we look at it visually, we can see at a glance that the shortest acceptable string is “BANC”, but how does the program determine that? You have to find all of the substrings of s that fit the criteria, all of the substrings of S that contain t, and then compare them and get the shortest ones. So our problem becomes: how do we get all the substrings that match the criteria?
Double cycle of violence
The simple observation is that the first two elements must be members of t, as long as they fit the shortest substring. So when you use double loop traversal, you can filter out a lot of elements that are not in t, and you can greatly reduce redundant traversal.
In combination with this, we can identify the starting point in the first loop and the end point in the second loop using the method mentioned above for checking inclusion, and finally get the correct result. Unsurprisingly, when you finish writing this code and click Submit, you get the following result:
How to do? Next up is the subject of this article, sliding Windows.
The sliding window
From the title we can get a glimpse, mention “minimum”, “cover” and so on, we can try to use the sliding window to solve this kind of problem (after all this talk, my title is written is sliding window deliberate exercise). What is a sliding window? A sliding window, as its name implies, is a window, but the left and right frame of the window can be moved, and the left and right frame is also what we often call the left and right Pointers. The key to using a sliding window in general is that we need to confirm a few things:
- When does the window on the right move?
- When does the window on the left move?
- Process values in the window
Clear these points, the sliding window problem is actually very simple, let’s combine the first example of this problem, to explore the charm of sliding Windows.
Enter: s ="ADOBECODEBANC", t = "ABC"Output:"BANC"
Copy the codeWhen does the window on the right move
In this case, the right window slides to the right when the s substring inside the window does not contain t.
When initialized, our window size is 0, in other words, the left pointer L and the available pointer R are both at the initial position 0. Our box has only one value, s[0].
"ABC".
l 到 rAnd that gives us our first substring, which we can store for the time being. What’s next? Next up is the show in the left window.
When does the window on the left move
When does the window on the left move? When the substring in the window already meets the condition, move the left window and compress the existing substring until the smallest substring is obtained. So we move the left window L to get the following:
l 和 rThe substring in between doesn’t satisfy this condition, so of course we have to start movingrBy this window. Repeat the process untilrthesThe character terminates at the end.
Process values in the window
There is a detail worth discussing here, which is when do we intercept strings and compare to find minima? So the shortest possible substring is going to be in the l pointer, which is the window on the left, and we’re going to get the shortest possible substring for r. So you can do your own coding and sort of figure it out.
The chopsticks 🥢
We started writing code along these lines:
// Gets the number of characters per target value, stored as an object
var generateMap = function (t) {
let tmap = {}
for (let key of t) {
if(tmap[key] ! =undefined) {
tmap[key]++
} else {
tmap[key] = 1}}return tmap
}
var minWindow = function (s, t) {
// Some boundary conditions
if (s.length < t.length) {
return ' '
}
// Some boundary conditions
if (s.indexOf(t) > -1) {
return t
}
let tmap = generateMap(t)
let minstr = ' '
let l = 0
let r = 0
let typenum = Object.keys(tmap).length
while (r < s.length) {
// Confirm the starting point
if(tmap[s[r]] ! =undefined) {
tmap[s[r]]--
// One type of character is completely overwritten
if (tmap[s[r]] == 0) {
typenum--
}
// Enter shrinkage process after full coverage
while (typenum == 0) {
// The left pointer encounters a value in map that increases typenum, breaking out of the l move loop and returning to the R move loop
if(tmap[s[l]] ! =undefined) {
tmap[s[l]]++
if (tmap[s[l]] == 1) {
// Intercepts a string
let newminstr = s.substring(l, r + 1)
// Compare the shortest oneminstr = (! minstr || newminstr.length <= minstr.length) ? newminstr : minstr typenum++ } } l++ } } r++ }return minstr
};
Copy the codeThe small voice BB
The difficulty of this problem is marked on the buckle. After self-study and analysis, I found that I can solve it. With the deepening of learning, I found that my fear of algorithms gradually decreased, which also verified that the unknown is the fear.
Recently, I participated in a 21-day punching training camp. I supervised everyone and myself to complete the daily tasks set at the beginning, including one algorithm problem every day. When I encountered this sliding window problem yesterday, I suddenly remembered that there was a piece in the gold digging draft box that I wanted to write at that time, but now it has long grey “Deliberately practicing sliding window”, just this topic is classic enough and has a certain difficulty. So I took some time to finish the flag that year. Although it was a little late, as I mentioned in the preface, on the way, it is good. So far, the New Year’s flag is still there.
Recently I am still reading a book about marketing, and there is a book “Those Things in the Ming Dynasty”. Now I have seen the part where Chongba abolishes the prime minister system. The following story should be more wonderful.
Recently looking forward to the latest words of one Piece king, want to see how strong luffy students after awakening. To see if the enduring final mystery turns out to be more unexpected than expected, or if the Hymie boys have already guessed the wrong thing.
Finally post a piece in the small broken station to see a fifth file hand, from here, invade delete!
🎉 🎉 if you think this article is helpful to you, please don’t hesitate to give your thumbs up ~🎉 🎉
🎉 🎉 If you have any questions or suggestions about the wording, knowledge and format of the article, please leave a comment ~🎉 🎉