假设我们有一个字符串s,我们必须对s的子字符串进行查询。对于每个查询查询[i],它分为三个部分[left,right,k],我们可以重新排列子字符串s [left],...,s [right],然后最多选择k个子字符串替换为任何小写英文字母。如果在上述操作之后子字符串可能是回文,则查询结果为true。否则为假。我们必须找到一个数组answer [],其中answer [i]是第i个查询query [i]的结果。
例如,如果输入为“ abcda”,则查询类似于[[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0, 4,1]],则输出将为[true,false,false,true,true]
为了解决这个问题,我们将遵循以下步骤-
定义一个名为Solve的方法,它将采用dp矩阵和q。这将如下所示工作-
l:= q [0],r:= q [1],k:= q [2],然后将l和r加1,一个:= 0
当我在0到25的范围内
一个:=一个+(dp [r,i] – dp [l – 1,i])mod 2
当整数除以1/2 <= k时返回true,否则返回false
定义另一个名为的方法makeDP()
,它将采用dp矩阵和s,其工作方式如下:
对于范围在0到s长度之间的i
dp [i,j]:= dp [i – 1,j]
适用于0到25范围内的j
将dp [i,s [i]的ASCII –'a'的ASCII]增加1
主要方法将是-
n:=字符串s的大小,s:=“”连接s
dp:=阶(n + 1)x 26的矩阵,并用0填充
调用makeDP(dp,s)
res:=长度与q长度相同的数组,并用false填充
对于i,范围为0至q – 1的长度
res [i]:= solve(dp,q [i])
返回资源
让我们看下面的实现以更好地理解-
class Solution(object): def solve(self,dp,q): l = q[0] r = q[1] k = q[2] r+=1 l+=1 #arr = [ 0 for i in range(26)] one = 0 for i in range(26): one += (dp[r][i]-dp[l-1][i])%2 return one//2<=k def make_dp(self,dp,s): for i in range(1,len(s)): for j in range(26): dp[i][j] = dp[i-1][j] dp[i][ord(s[i])-ord('a')]+=1 def canMakePaliQueries(self, s, q): n = len(s) s = " "+s dp = [[0 for i in range(26)] for j in range(n+1)] self.make_dp(dp,s) res = [False for i in range(len(q))] for i in range(len(q)): res[i] = self.solve(dp,q[i]) return res ob = Solution()print(ob.canMakePaliQueries("abcda", [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]))
"abcda" [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
输出结果
[True, False, False, True, True]