RSS Feed

September, 2015

  1. 子序列中的滑动窗口

    September 28, 2015 by xudifsd

    很多子序列题都可以用滑动窗口解决,这个方案适用于需要找一个子序列的开始和结束位置。注意,这里指的子序列类似于子字符串,而非subsequence

    例如 leetcode 的 Substring with Concatenation of All Words 。最简单的方法就是找到一个开始位置,然后判断这个位置是否可行,代码如下:

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    #!/usr/bin/env python
    
    class Solution:
        def findSubstring(self, s, words):
            if len(words) == 0 or len(s) == 0:
                return []
            dic = {}
            count = 0
            for w in words:
                dic[w] = dic.get(w, 0) + 1
                count += 1
            lw = len(words[0])
            lws = lw * len(words)
            result = []
            for i in xrange(len(s) - lws + 1):
                if self.possible(s, lw, i, dic, count):
                    result.append(i)
            return result
    
        def possible(self, s, lw, i, dic, count):
            dic2 = dic.copy()
            if count == 0:
                return True
            while count > 0:
                cur = s[i:i+lw]
                if dic2.get(cur) != None and dic2.get(cur) > 0:
                    dic2[cur] -= 1
                    if dic2[cur] < 0:
                        return False
                    count -= 1
                    i += lw
                else:
                    return False
            return True
    

    但是时间复杂度度也很高,有O(n2),这里面有很多冗余计算,比如对于输入

    “aabbccaadd”, [“aa”, “bb”, “cc”, “dd”]

    就会处理 “bbccaa” 两次。最好的办法是使用滑动窗口:维护开始和结束位置,一旦开始和结束位置一样就退出循环,否则在可行的情况下增加结束位置,如果不可行则增加开始位置。

    滑动窗口可以将复杂度降低到O(n)。在这一题中,由于字典中的字符串都是同样大小,所以可以以这个大小作为步长移动。但是需要添加另一个循环来覆盖以不同的偏移开始计算的情况。代码如下:

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    #!/usr/bin/env python
    
    class Solution(object):
        def findSubstring(self, s, words):
            if len(s) == 0 or len(words) == 0:
                return []
            m = {}
            count = 0
            for w in words:
                m[w] = m.get(w, 0) + 1
                count += 1
            lw = len(words[0])
            result = []
            for delta in xrange(lw):
                i = delta
                while i < len(s) - lw + 1:
                    key = s[i:i + lw]
                    if m.get(key) > 0:
                        m[key] -= 1
                        count -= 1
                        j = i + lw
                        while i < j:
                            if count == 0:
                                result.append(i)
                            if j < len(s) - lw + 1:
                                key = s[j:j + lw]
                                if m.get(key) > 0:
                                    m[key] -= 1
                                    count -= 1
                                    j += lw
                                    continue
                            m[s[i:i + lw]] += 1
                            count += 1
                            i += lw
                    else:
                        i += lw
            return result
    

    其中,for循环用来处理不同偏移的情况,for循环中的循环用于实现滑动窗口。这个实现复杂度为O(lw * n),如果将lw看成常数则复杂度为O(n)。

    滑动窗口适用于很多子序列类的算法,如:Minimum Size Subarray SumMinimum Window SubstringLongest Substring Without Repeating Characters