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