当前位置:网站首页>Leetcode hot topic Hot 100 day 32: "minimum coverage substring"
Leetcode hot topic Hot 100 day 32: "minimum coverage substring"
2022-07-06 20:32:00 【Ultimate brocade】
Continue to brush LeetCode Hot topic HOT 100 The subject of , And update my blog solutions. stay csdn In my blog, I will try to explain clearly in words , relevant Java Code, you can go to my Personal blog jinhuaiyu.com View in .
subject : Minimum cover substring
Give you a string s 、 A string t . return s Covered by t The smallest string of all characters . If s There is no coverage in t Substring of all characters , Returns an empty string “” .
Be careful :
about t Duplicate characters in , The number of characters in the substring we are looking for must not be less than t The number of characters in the .
If s There is such a substring in , We guarantee that it is the only answer .
Example 1:
Input :s = “ADOBECODEBANC”, t = “ABC”
Output :“BANC”
Example 2:
Input :s = “a”, t = “a”
Output :“a”
Example 3:
Input : s = “a”, t = “aa”
Output : “”
explain : t Two characters in ‘a’ Shall be included in s In the string of ,
Therefore, there is no qualified substring , Returns an empty string .
Tips :
1 <= s.length, t.length <= 105
s and t It's made up of English letters
Advanced : You can design one in o(n) The algorithm to solve this problem in time ?
solution: The sliding window
If we use violence to solve this problem , Each time we discuss the qualified substring with a position character as the initial character , You need to O(n²) Time complexity of . The optimization point is if you find a cover string , Then in the inner loop, the characters on the right side don't need to be traversed ( The initial character is fixed ), Because the longer length is not what we require . But the time complexity has not changed . Can the minimum covering substring of this fixed initial character continue to the next in the outer loop ( The initial character is shifted one bit to the right ) Continue to use ? In this case, the inner loop is no longer traversed from the initial character . This is the idea of sliding window in this problem .
Imagine in a string s There is a sliding window on the , At first, the left pointer is at the first character , The right pointer starts traversing from left to right , Until you just get to a certain position , The overwritten characters contain strings t All the characters in . At this point, we get a possible result , We recorded . Next, the right pointer does not move , The left pointer starts to move right , Until it just destroys the previous conditions ( The window no longer contains s All characters ), In the process of moving the left pointer to the right ( Not including when the best conditions are not tenable ), You will get some smaller coverage substrings , It can be used to update the results .
The left pointer no longer moves , Start moving the right pointer to the right again , Until it meets the conditions when it reaches a certain position , Then move the left pointer , This process is the same as before . We can find out , First move the right pointer to find the tail of the covering substring , When the left pointer moves, all qualified substrings will be found , In this process, we always maintain the smallest covering substring . Finally, the left and right pointers traverse the string s, Find the minimum covering substring , But there are two cycles in this process ( The outer loop moves the right pointer to find the qualified substring , Move the left pointer in an inner loop to minimize the coverage ), But the left and right pointers just moved from left to right n position , The time complexity of this process is O(n).
How to be in O(n) Determine whether the window contains t String ? We can use two hash The table stores the window and the string respectively t The number of corresponding characters in ( Window hash There is no need to store tables t Characters not in , Reduce storage space ), When comparing, you can use iterators in O(n) Compare the two within the time complexity hash surface .
Finally, The code with detailed comments is placed in my Personal blog http://jinhuaiyu.com/leetcode-minimum-window-substring/
边栏推荐
猜你喜欢
持续测试(CT)实战经验分享
Error analysis ~csdn rebound shell error
小孩子學什麼編程?
Pytest (3) - Test naming rules
HMS core machine learning service creates a new "sound" state of simultaneous interpreting translation, and AI makes international exchanges smoother
Application layer of tcp/ip protocol cluster
【云原生与5G】微服务加持5G核心网
[weekly pit] calculate the sum of primes within 100 + [answer] output triangle
BeagleBoneBlack 上手记
Utilisation de l'écran OLED
随机推荐
(工作记录)2020年3月11日至2021年3月15日
JVM_ Common [interview questions]
"Penalty kick" games
Crawler (14) - scrape redis distributed crawler (1) | detailed explanation
Build your own application based on Google's open source tensorflow object detection API video object recognition system (IV)
02 basic introduction - data package expansion
【计网】第三章 数据链路层(4)局域网、以太网、无线局域网、VLAN
Problems encountered in using RT thread component fish
[weekly pit] positive integer factorization prime factor + [solution] calculate the sum of prime numbers within 100
APS taps home appliance industry into new growth points
Node.js: express + MySQL实现注册登录,身份认证
枚举根据参数获取值
How to upgrade high value-added links in the textile and clothing industry? APS to help
PowerPivot - DAX (first time)
[network planning] Chapter 3 data link layer (3) channel division medium access control
(work record) March 11, 2020 to March 15, 2021
7、数据权限注解
rt-thread i2c 使用教程
数字三角形模型 AcWing 1018. 最低通行费
Anaconda安装后Jupyter launch 没反应&网页打开运行没执行