Problem
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
1 | Example: |
- If there is no such window in S that covers all characters in T, return the empty string “”.
- If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
给定两个字符串S,T, 在串S中找到包含T串中所有字符的最短子串. 时间复杂度要求O(N).
时间复杂度给定了一个具体的要求.线性时间. 所以暴力破解是不可行的. 要求S的子串包含组成T的所有字符,没有顺序的要求,只要包含就行.T串字符可能会有重复元素存在. 所以使用一个unordered_map哈希表来记录T.
Solution
Analysis
具体做法,就是先记录T的组成.然后遍历S串,找到一个解之后,更新左边界,因为这个解当中可能会存在无关元素,以及重复元素.
最短: 通过一个全局变量,记录当前解的长度,及时更新这个变量,最后找到最终解.
Code
1 | class Solution { |