python - 查找一个字符串在另一个字符串中的所有排列

Question

我有一个字符串，例如:string1 = 'abcdbcabdcabb'。我还有另一个字符串，例如: string2 = 'cab'

我需要计算 string1 中 string2 的所有排列。

目前我正在将 string2 的所有排列添加到列表中，然后通过 index+string.size 迭代抛出 string1 并检查如果 string1 的子字符串包含在排列列表中

我确信有更好的优化方法来做到这一点。

Answer 1

在我看来你需要的不是DP，而是滑动窗口技术。 string2 的排列是长度完全相同且字符分布相同的字符串。在 string2 的示例中，排列是。长度为 3 且字符分布如下的字符串:{a:1,b:1,c:1}。

因此，您可以编写一个脚本，从 string1(index=0) 的开头考虑一个大小为 N(string2 的大小)的窗口。如果当前窗口具有完全相同的字符分布，则接受它作为排列，如果不是，则不计算它，然后继续索引+1。

一个不重新计算每个滑动窗口中字符分布的技巧，你可以得到一个字符字典，并在第一个窗口中统计字符，然后当你向右滑动窗口时，减少删除的字符加1，添加字符加1。

代码应该是这样的，您需要验证它的边缘情况:

def get_permut(string1,string2):
    N =len(string2)
    M = len(string1)

    if M < N:
        return 0


    valid_dist = dict()
    for ch in string2:
        valid_dist.setdefault(ch,0)
        valid_dist[ch]+=1
    
    current_dist=dict()
    for ch in string1[:N]:
        current_dist.setdefault(ch,0)
        current_dist[ch]+=1
    
    ct=0
    for i in range(M-N):
        if current_dist == valid_dist:
            ct+=1
        current_dist[i]-=1
        current_dist.setdefault(i+1,0)
        current_dist[i+1]+=1
        if current_dist[i]==0:
            del current_dist[i]
    
    return ct