今際の国の呵呵君
Saturday, October 28, 2017
[LeetCode]Minimum Window Substring
和之前各种
sliding window
的题都是类似的,区别就是这一题策略稍微不同,要求最短的,所以我们每次就得尽量将左边界右移,具体策略如下:
如果当前s的substring没有包含t的所有字符,右移右边界
如果包含了t的所有字符,假设左边界对应的字符为left
如果substring中left的数量大于t中的数量,右移左边界
如果left不为t中的字符,右移左边界
这样可以保证我们每次找到满足条件最短的,时间复杂度O(n),空间复杂度O)(n),代码如下:
No comments:
Post a Comment
Newer Post
Older Post
Home
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment