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

Question

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

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

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

我确定有更好的优化方法。

Answer 1

您可以为此使用正则表达式。


def lst_permutation(text):
    from itertools import permutations
    lst_p=[]
    for i in permutations(text):
        lst_p.append(''.join(i))
    return lst_p

def total_permutation(string1,string2):
    import re
    total=0
    for i in lst_permutation(string2):
        res=re.findall(string2,string1)
        total += len(res)
    return total


string1 = 'abcdbcabdcabb'
string2 = 'cab'
print(total_permutation(string1,string2))
#12

Answer 2

您可以在此处使用 string.count() 方法。请参阅下面的一些解决方法：

import itertools
perms=[''.join(i) for i in itertools.permutations(string2)]

res=0

for i in perms:
    res+= string1.count(i)

print(res)
# 4

Answer 3

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

所以你可以写一个脚本，考虑一个 window 大小为 N（string2 的大小），从 string1(index=0) 开始。如果你当前的 window 具有完全相同的字符分布，你接受它作为一个排列，如果不是你不计算它，你继续 index+1.

每次滑动不重新计算字符分布的技巧window，可以得到一个字符字典，统计最开始的字符window，然后滑动window 向右一位，您将删除字符减一，将添加字符增加一。

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

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

Answer 4

这是使用正则表达式执行此操作的愚蠢方法（实际上不要这样做）。

对搜索文本中的每个字母使用非捕获组，然后期望每个捕获组中的一个出现在输出中：

import re

string1 = 'abcdbcabdcabb'
string2 = r'(?:c()|a()|b()){3}'


pos = 0
r = re.compile(string2)
while m := r.search(string1, pos=pos):
    print(m.group())
    pos = m.start() + 1

abc
bca
cab
cab

也可以动态生成

import re

string1 = 'abcdbcabdcabb'
string2 = 'cab'

before = "|".join([f"{l}()" for l in string2])
matches = "".join([f"\{i + 1}" for i in range(len(string2))])
r = re.compile(f"(?:{before}){{{len(string2)}}}{matches}")

pos = 0
while m := r.search(string1, pos=pos):
    print(m.group())
    pos = m.start() + 1

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

Find all permutation of a string in another string

python

algorithm

dynamic-programming