算法-滑动窗口解决子串问题

问题描述:

给出string, 和target两个字符串, 找出target在string中的起始位置, 顺序无所谓
比如: string = ‘abckdacabcd’ , target = ‘aabc’, 那么符合条件的子串应该是 acab, 起始位置是5

    # 用滑动窗口思想解决这个问题
    def find_target_in_string(string, target):
        target_len = len(target)
        target_map = {}
        # 目标子串各字符数量map
        for item in target:
            if item in target_map:
                target_map[item] += 1
            else:
                target_map[item] = 1
        # 关于invalid的定义: a)不在target_map中的, b)在target_map中但是数量多于需求的
        invalid = 0
        left = 0
        for right in range(len(string)):
            # 查看第一个窗口是否符合条件
            if right < target_len:
                if string[right] in target_map:
                    target_map[string[right]] -= 1
                    if target_map[string[right]] < 0:
                        invalid += 1
                else:
                    invalid += 1
                continue

            if invalid == 0:
                break
            # 窗口右侧进入一个
            if string[right] in target_map:
                target_map[string[right]] -= 1
                # 进来后发现比需求的多, invalid+1
                if target_map[string[right]] < 0:
                    invalid += 1
            else:
                invalid += 1
            # 窗口左侧出去一个
            if string[left] in target_map:
                # 如果出去之前不是invalid, 证明, 此处出窗口操作并未对invalid数量造成实际影响
                # 所以此处出窗口前是invalid的, invalid-1
                if target_map[string[left]] < 0:
                    invalid -= 1
                target_map[string[left]] += 1
            else:
                invalid -= 1
            left += 1

        if invalid != 0:
            print('Not found')
            return -1
        else:
            print(left, left+target_len-1)
            print(string[left:left+target_len])
            return left