数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学Python 中查找长度为 K 且无重复字符的子字符串
假设我们有一个字符串 S，我们需要找到长度为 K 且没有重复字符的子字符串的数量。例如，如果 S = “heyfriendshowareyou” 且 K 为 5，则输出将为 15，因为这些字符串是 [heyfr, eyfri, yfrie, frien, riend, iends, endsh, ndsho, dshow, showa, howar, oware, warey, areyo, reyou]
为了解决这个问题，我们将遵循以下步骤：
- 创建一个空映射 m，并设置 left := 0，right := -1 和 ans := 0
- 当 right < 字符串长度 – 1 时
- 如果 right – left + 1 = k，则
- 将 ans 加 1
- 将 m[str[left]] 减 1
- 将 left 加 1
- 继续下一个迭代
- 如果 str[right + 1] 不在 m 中，则
- 设置 m[str[right + 1]] := 1
- 将 right 加 1
- 否则如果 m[str[right + 1]] 为 0，则
- 将 m[str[right + 1]] 加 1
- 将 right 加 1
- 否则
- 将 m[str[left]] 减 1
- left := left + 1
- 如果 right – left + 1 = k，则
- 如果 right – left + 1 = k，则将 ans 加 1
- 返回 ans
示例
让我们来看下面的实现来更好地理解：
class Solution(object):
def numKLenSubstrNoRepeats(self, S, K):
m = {}
left = 0
right = -1
ans = 0
while right<len(S)-1:
if right - left + 1 == K:
ans+=1
m[S[left]]-=1
left+=1
continue
if S[right+1] not in m :
m[S[right+1]]=1
right+=1
elif not m[S[right+1]]:
m[S[right+1]]+=1
right+=1
else:
m[S[left]]-=1
left+=1
if right - left + 1 == K:
ans+=1
return ans
ob1 = Solution()
print(ob1.numKLenSubstrNoRepeats("heyfriendshowareyou", 5))输入
"heyfriendshowareyou" 5
输出
"AIIOC"
更新于：2020年4月29日
446 次浏览
广告