注册一个网站需要多少钱,流量精灵,中国最好的包装设计公司,建一个做笔记的网站Leetcode 2953. Count Complete Substrings 1. 解题思路2. 代码实现 题目链接#xff1a;2953. Count Complete Substrings
1. 解题思路
这一题麻烦的点就在于说有两个限制条件#xff0c;但是好的点在于说这两个限制条件事实上是相互独立的。
因此#xff0c;我们可以通…Leetcode 2953. Count Complete Substrings 1. 解题思路2. 代码实现 题目链接2953. Count Complete Substrings
1. 解题思路
这一题麻烦的点就在于说有两个限制条件但是好的点在于说这两个限制条件事实上是相互独立的。
因此我们可以通过第二个限制条件将字符串进行分段此时目标子串必然在各个分段字符串之内且此时我们只需要考虑第一个限制条件即可。
而对于第一个限制条件一个简单的思路就是对26个字符建一个counter然后分别对每一个位置作为起始点的情况进行考察。
显然如果要成立那么目标字符串长度一定是 k k k的倍数且如果任何一个字符的个数超过 k k k时就一定不成立。
但是直接这样的实现我们发现会出现超时因此我们加了一些奇技淫巧用于优化算法主要就是对于只有一个字符的情况进行了一下优化因为如果只有一个字符的话那么可能的个数就一定是 n − k 1 n-k1 n−k1个。
2. 代码实现
给出python代码实现如下
class Solution:def countCompleteSubstrings(self, word: str, k: int) - int:def count_complete(s):n len(s)if n k:return 0if len(set(s)) 1:return n-k1cnt [[0 for _ in range(26)] for _ in range(n1)]for i, ch in enumerate(s):for j in range(26):cnt[i1][j] cnt[i][j]cnt[i1][ord(ch) - ord(a)] 1ans 0for i in range(n-k1):j ikwhile j n:diff [y-x for x, y in zip(cnt[i], cnt[j])]if any(x k for x in diff):breakif all(x k or x 0 for x in diff):ans 1j kreturn ansidx 0i, n 0, len(word)ans 0while i n-1:if abs(ord(word[i]) - ord(word[i1])) 2:ans count_complete(word[idx:i1])idx i1i 1ans count_complete(word[idx:])return ans提交代码评测得到耗时6583ms占用内存582.8MB。
