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

Question

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

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

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

我相信有一种更好的优化方法可以做到这一点

Answer 1

在我看来，您不需要DP，而是需要一种滑动窗口技术。字符串2的排列是一个长度完全相同且字符分布相同的字符串。在字符串2的例子中，置换是.一个长度为3的字符串，具有以下字符分布：｛a:1，b:1，c:1｝。

因此，您可以编写一个脚本，考虑从字符串1(index=0(开始的大小为N(字符串2的大小(的窗口。如果当前窗口具有完全相同的字符分布，则接受它作为排列，如果不接受，则不计算它，然后转到索引+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

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

您可以使用regex。

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 4

这里有一种使用regex的愚蠢方法(不要实际这样做(。

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

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

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