子串置换复杂度

Question

刚刚有一个关于 Python 实现的关于子字符串排列的 Leetcode 问题的快速问题，因为我是算法的主要新手：

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

示例 1：

Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").

示例 2：

Input:s1= "ab" s2 = "eidboaoo"
Output: False

根据给出的其中一种解决方案，我认为以下时间复杂度为O(n)，但时间复杂度是否为O(1)？此外，有人会提供 Python 实施蛮力方法的资源吗？谢谢！

from collections import Counter

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        s1_count, s2_count = Counter(s1), Counter(s2[:len(s1)])
        
        for i in range(len(s2)-len(s1)):
            if s1_count == s2_count: 
                return True
            
            if s2_count[s2[i]] == 1: 
                del s2_count[s2[i]]
            else: 
                s2_count[s2[i]] -= 1
            
            if s2[i+len(s1)] in s2_count: 
                s2_count[s2[i+len(s1)]] += 1
            else: 
                s2_count[s2[i+len(s1)]] = 1
                
        return s1_count == s2_count
        
sol = Solution()
print(sol.checkInclusion('ab', 'eidbaooo'))

Answer 1

我认为最佳解决方案是 O(n)，因为您需要在 s2 中搜索 s1 的所有组合。这是一个简明的 python 解决方案：

from itertools import permutations

def find_subs(s1,s2):
    perms = [''.join(p) for p in permutations(s1)] # create all possible permutations of s1
    for p in perms: 
        if p in s2: #search it in s2
            return True
    return False

find_subs('ab',"eidbaooo")

True

Answer 2

您自己的解决方案的时间复杂度似乎是 O(n)，因为时间与输入的长度成正比。 O(1) 意味着输入的大小无关紧要，这里不是这种情况。创建和搜索 inputvector 的答案中的所有可能的排列是您要求的蛮力方法，当 len(s1) 超过 10 时它非常慢。这具有非常快速增长的时间复杂度 O(n!)。

我忍不住想打败你的算法。结果我做不到。这是我的尝试。对于 s1 中最多约 6 个字符的短字符串，它的速度要快一些。它具有 O(n²) 时间复杂度。

def checkInclusion2(s1,s2):
    i = -1
    max_i = len(s2)-len(s1)+1
    while i < max_i:
        i += 1
        c = s2[i]
        if not c in s1:
            continue
        temp = list(s1)
        temp.remove(c)
        for j, c in enumerate(s2[i+1:i+len(s1)]):
            if c in temp:
                temp.remove(c)
            else:
                if c not in s1:
                    i += j
                break
        else:
            return True
    return False

所以，然后我尝试优化你的，发现比较 defaultdicts 比 Counters 更快。将 s2 中的字符保存在一个临时变量中比多次获取它要快。这是两倍的速度，但通常不算时间复杂度。还是O(n).

from collections import defaultdict

def checkInclusion3(s1, s2):
    s1_count, s2_count = defaultdict(int), defaultdict(int)
    for i in range(len(s1)):
        s1_count[s1[i]] += 1
        s2_count[s2[i]] += 1
    for i in range(len(s2)-len(s1)):
        if s1_count == s2_count: 
            return True
        old_c = s2[i]
        if s2_count[old_c] == 1:
            del s2_count[old_c]
        else:
            s2_count[old_c] -= 1
        s2_count[s2[i+len(s1)]] += 1
    return s1_count == s2_count

子串置换复杂度

Substring permutation complexity

python

time-complexity

space-complexity