欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Python求解在一个字符串中找到重组子串

程序员文章站 2023-12-26 23:58:27
给定一个字符串s和一个非空子串p,找到所有p的重组字符串在s中出现的初始位置。该字符串全部由小写字母组成,s和p的长度都不超过20100.输出的顺序不重要。例:s:‘cbaebabacd’. p:‘abc’ . 输出:[0:6]解题思路,一般在字符串中不考虑顺序,都会要用到字典或者是set,counter。找到全部重组子串,维护两个集合,每次进行滑动窗口的判断,记录位置。def findanagrams(s):res=[]#将p字符串放入到counter集合中,同时在s字符p长度-1的子...

给定一个字符串s和一个非空子串p,找到所有p的重组字符串在s中出现的初始位置。该字符串全部由小写字母组成,s和p的长度都不超过20100.输出的顺序不重要。

例:s:‘cbaebabacd’. p:‘abc’ . 输出:[0:6]

解题思路,一般在字符串中不考虑顺序,都会要用到字典或者是set,counter。找到全部重组子串,维护两个集合,每次进行滑动窗口的判断,记录位置。

def findanagrams(s):
	res=[]
	#将p字符串放入到counter集合中,同时在s字符p长度-1的子字符串
	s_set = Counter(s[:len(p)-1])
	p_set = Counter(p)
	for i in range(len(p)-1,len(s)):
		s_set[s[i]]+=1
		#判断s_set和p_set是否相等
		if s_set == p_set:
			res.append(i-len(p)+1)
		#将第一个字符从集合s_set中删除掉,缩小窗口
		s_set[s[i-len(p)+1]]-=1
		if s_set[s[i-len(p)+1]]==0
			del s_set[s[i-len(p)+1]]
	return res

本文地址:https://blog.csdn.net/jhsignal/article/details/107353394

上一篇:

下一篇: